Mereghetti, Carlo; Pighizzini, Giovanni Optimal simulations between unary automata. (English) Zbl 0980.68048 SIAM J. Comput. 30, No. 6, 1976-1992 (2001). Summary: We consider the problem of computing the costs – in terms of states – of optimal simulations between different kinds of finite automata recognizing unary languages. Our main result is a tight simulation of unary \(n\)-state two-way nondeterministic automata by \(O(e^{\sqrt{n\ln n}})\)-state one-way deterministic automata. In addition, we show that, given a unary \(n\)-state two-way nondeterministic automaton, one can construct an equivalent \(O(n^2)\)-state two-way nondeterministic automaton performing both input head reversals and nondeterministic choices only at the ends of the input tape. Further results on simulating unary one-way alternating finite automata are also discussed. Cited in 2 ReviewsCited in 46 Documents MSC: 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) 68Q45 Formal languages and automata Keywords:formal languages; deterministic; nondeterministic; and alternating finite state automata; unary languages PDFBibTeX XMLCite \textit{C. Mereghetti} and \textit{G. Pighizzini}, SIAM J. Comput. 30, No. 6, 1976--1992 (2001; Zbl 0980.68048) Full Text: DOI