A quadratic lower bound for 2DFAs against one-way liveness
2026-02-27 • Formal Languages and Automata Theory
Formal Languages and Automata Theory
AI summaryⓘ
The authors show that any two-way deterministic finite automaton (2DFA) designed to solve a specific problem called one-way liveness on inputs of size h needs at least on the order of h squared states. This sets a strong limit on how much smaller a 2DFA can be compared to one-way nondeterministic finite automata (NFAs) when converting between them. Their result matches a famous earlier lower bound by Chrobak but works for alphabets of any size, not just unary ones. They also introduce a general proof technique that could be useful for other problems.
two-way deterministic finite automatonone-way livenessstate complexitynondeterministic finite automatonlower boundsChrobak's theoremunary languagesautomata conversionalphabet sizecomputational complexity
Authors
Kehinde Adeogun, Christos Kapoutsis
Abstract
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.