Intersecting Dense Automata: Constructions, Complexity and Certificates

Given k nondeterministic finite automata (NFA), finding an NFA that recognises the intersection of their languages is a basic problem in automata theory. We observe that the classical Cartesian product construction is non-optimal in the worst case, that is, if the automata have many transitions. For a fixed alphabet, the Cartesian product of two NFA may have Θ(m²) transitions if these NFA have at most n states and m transitions each. In this talk, we describe alternative constructions with O(mn) transitions; or O(mn^(k − 1)) for the intersection of k NFA (for fixed k ≥ 2 and alphabet Σ). This gives a faster algorithm for deciding NFA intersection emptiness, that is, deciding whether k given NFA accept a word in common.

We also show that this new algorithm is optimal, unless there exists a breakthrough combinatorial algorithm for detecting (k + 1)-cliques in undirected graphs.

Lastly, we show how these new product constructions allow us to certify NFA intersection emptiness faster.