A quadratic lower bound for 2DFAs against one-way liveness
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914358006644736 |
|---|---|
| author | Adeogun, Kehinde Kapoutsis, Christos |
| author_facet | Adeogun, Kehinde Kapoutsis, Christos |
| contents | We show that every two-way deterministic finite automaton (2DFA) that solves one-way liveness on height h has Omega(h^2) states. This implies a quadratic lower bound for converting one-way nondeterministic finite automata to 2DFAs, which asymptotically matches Chrobak's well-known lower bound for this conversion on unary languages. In contrast to Chrobak's simple proof, which relies on a 2DFA's inability to differentiate between any two sufficiently distant locations in a unary input, our argument works on alphabets of arbitrary size and is structured around a main lemma that is general enough to potentially be reused elsewhere. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_24279 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A quadratic lower bound for 2DFAs against one-way liveness Adeogun, Kehinde Kapoutsis, Christos Formal Languages and Automata Theory We show that every two-way deterministic finite automaton (2DFA) that solves one-way liveness on height h has Omega(h^2) states. This implies a quadratic lower bound for converting one-way nondeterministic finite automata to 2DFAs, which asymptotically matches Chrobak's well-known lower bound for this conversion on unary languages. In contrast to Chrobak's simple proof, which relies on a 2DFA's inability to differentiate between any two sufficiently distant locations in a unary input, our argument works on alphabets of arbitrary size and is structured around a main lemma that is general enough to potentially be reused elsewhere. |
| title | A quadratic lower bound for 2DFAs against one-way liveness |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2602.24279 |