Intersecting Dense Automata

2026/05/19 by Dmitry Chistikov, Neha Rino · 1 voice
Computer Science · #cs.FL #cs.LO

paper · pdf · doi:10.48550/arxiv.2605.20421

Abstract

We observe that the classical Cartesian product construction for the intersection of (languages of) nondeterministic finite automata (NFA) is non-optimal in the worst case, if the automata have many transitions. For a fixed alphabet, the product of two NFA may have Θ(m²) transitions if these NFA have at most n states and m transitions each. We describe alternative constructions with O(m n) transitions: or O(m n^k-1) for the intersection of k NFA (for fixed k ≥ 2 and alphabet Σ). This gives a faster algorithm for deciding NFA intersection emptiness. The new algorithm is optimal, unless there exists a breakthrough combinatorial algorithm for detecting (k+1)-cliques in undirected graphs. This also leads to a more efficient certification scheme for NFA intersection emptiness.

Citations

• Faster Combinatorial k-Clique Algorithms
• The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems
• The n-ary Initial Literal and Literal Shuffle
• Lengths of Words Accepted by Nondeterministic Finite Automata
• If the Current Clique Algorithms are Optimal, so is Valiant's Parser
• Shuffling and Unshuffling
• Complexity of k-SAT
• Lower bounds for natural proof systems
• Finite Automata and Their Decision Problems

Discussions

• Dmitry Chistikov, Neha Rino: Intersecting Dense Automata https://arxiv.org/abs/2605.20421 https://arxiv.org/pdf/2605.20421 https://arxiv.org/html/2605.20421 [bsky, 0 points, 0 comments]

Related

• Finite Automata Intersection Non-Emptiness: Parameterized Complexity Revisited
• On the Complexity of Intersection Non-emptiness for Star-Free Language Classes
• Synchronizing non-deterministic finite automata
• On Complementing Unambiguous Automata and Graphs With Many Cliques and Cocliques
• Asynchronous Multi-Tape Automata Intersection: Undecidability and Approximation