{"id":"openai-math/An-exponential-two-way-deterministic-state-lower-bound-for-one-way-liveness","pdf":"https://github.com/openai/math/blob/main/preprints/An-exponential-two-way-deterministic-state-lower-bound-for-one-way-liveness-September-25-2026/main.pdf","url":"https://github.com/openai/math/tree/main/preprints/An-exponential-two-way-deterministic-state-lower-bound-for-one-way-liveness-September-25-2026","tags":["automata-theory","computational-complexity"],"score":0,"title":"An exponential two-way deterministic state lower bound for one-way liveness","domain":"Theoretical computer science","family":"129","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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 $`h+3`$ states and no left moves, whereas every equivalent s -state two-way deterministic automaton satisfies $`4(s+2)^2\\ge2^{\\lfloor(h-2)/31\\rfloor}`$. 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{},"formalized":true,"family_title":"Exponential state costs for two-way automata"}