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.