Abstract of Paper |
Converting Two--Way
Nondeterministic Unary Automata into Simpler Automata
by Viliam Geffert, Carlo
Mereghetti, and Giovanni Pighizzini
Abstract
We show that, on inputs of length exceeding $5n^2$, any $n$--state unary 2nfa (two--way nondeterministic finite automaton) can be simulated by a $(2n + 2)$--state quasi sweeping 2nfa. Such a result, besides providing a ``normal form'' for 2nfa's, enables us to get a subexponential simulation of unary 2nfa's by 2dfa's (two--way deterministic finite automata). In fact, we prove that any $n$--state unary 2nfa can be simulated by a 2dfa with $O(n^{\log n+4})$ states.