×

Optimal simulations between unary automata. (English) Zbl 0980.68048

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.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI