arXiv:2602.24279 · v3
A quadratic lower bound for 2DFAs against one-way liveness
摘要
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 can be applied to inputs over any alphabet and is structured around a main lemma that is general enough to potentially be reused elsewhere.
作者备注：17 pages, 4 figures, conference version presented at SOFSEM 2026, this version to be submitted to DMTCS's special issue for SOFSEM 2026