We consider the problem of computing the costs-in terms of states-of optimal simulations between different kinds of finite automata recognizing unary languaes. Our main result is a tight simulation of unary n-state two-way nondeterministic automata by O(e sup square root of (n ln n))-state one-way deterministic automata. In addition, we show that, given a unary n-stte two-way nondeterministic automaton, one can construct an equivalent O(n sup 2)-state two-way nondeterministic automaton performing both input head reversals and nondterministic choices at the endmarkers only. Further results on simulating unary alernating finite automata are pointed out. Our results give answers to some questions left open in the literature.
展开▼
