Family 129Theoretical computer scienceLeanNot yet digested
Exponential state costs for two-way automata
Proves exponential lower bounds both for complementing two-way nondeterministic finite automata and for simulating one-way nondeterministic automata by two-way deterministic ones. The latter resolves the Sakoda–Sipser state-succinctness conjecture over growing finite alphabets; both results rule out polynomial state bounds independent of alphabet size.
Manuscripts in this family · 2
An exponential state lower bound for two-way nondeterministic complementation
Sep 25, 2026·paper.pdfLean
We prove that two-way nondeterministic finite automata cannot be complemented with a polynomial number of states independent of the alphabet. For each n ≥ 4 we construct an n-state automaton over a finite alphabet whose complement requires at least states.
An exponential two-way deterministic state lower bound for one-way liveness
Sep 25, 2026·main.pdfLean
One-way liveness on h points accepts a word of binary relations when their ordered product is nonempty. For every h ≥ 2, it has a nondeterministic automaton with states and no left moves, whereas every equivalent s-state two-way deterministic automaton satisfies . Partial transition rules, stay moves, and nonaccepting infinite computations are allowed. The alphabets are finite and grow with h, so the result rules out an alphabet-independent polynomial state bound for deterministic two-way simulation, already for one-way nondeterministic sources.