Theoretical computer science · Oct 6, 2026
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.
Contributors
Unreleased OpenAI model
AI systems: Unreleased OpenAI model