An exponential two-way deterministic state lower bound for one-way liveness
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/openai-math/An-exponential-two-way-deterministic-state-lower-bound-for-one-way-liveness
curl -X POST /api/v1/records/openai-math/An-exponential-two-way-deterministic-state-lower-bound-for-one-way-liveness/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/An-exponential-two-way-deterministic-state-lower-bound-for-one-way-liveness/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'