## Optimal Simulations Between Unary Automata

#### Carlo Mereghetti and Giovanni Pighizzini

###### Dipartimento di Scienze dell'Informazione

Università degli Studi di Milano

via Comelico 39 -- 20135 Milano, Italy

##### Abstract

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 at the endmarkers only.
Further results on simulating unary alternating finite automata are pointed
out.
Our results give answers to some questions left open in the literature.

**Download**

Compressed postscript

Compressed dvi