Intersecting Dense Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914581455044608 |
|---|---|
| author | Chistikov, Dmitry Rino, Neha |
| author_facet | Chistikov, Dmitry Rino, Neha |
| contents | 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^2)$ 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 \ge 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_20421 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Intersecting Dense Automata Chistikov, Dmitry Rino, Neha Formal Languages and Automata Theory Logic in Computer Science 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^2)$ 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 \ge 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. |
| title | Intersecting Dense Automata |
| topic | Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2605.20421 |