A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata

Semyon Petrov, Alexander Okhotin

This paper establishes a lower bound on the number of states necessary in the worst case to simulate an $n$-state two-way nondeterministic finite automaton (2NFA) by a one-way unam…