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\ge 2^{\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 sources.