Unary Automata Simulations and Cyclic Languages

Carlo Mereghetti and Giovanni Pighizzini

Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy
A tight lower bound on the number of states of two-way deterministic and nondeterministic automata accepting unary languages is proved. This result represents a useful tool to study the cost --- in terms of states --- of the simulations of two-way automata with other kinds of automata and vice versa. We also show that any one-way nondeterministic automaton accepting a unary cyclic language can be simulated by a two--way deterministic automaton without increasing the number of states. This improves the quadratic simulation known for unary languages. Furthermore, by using the above mentioned lower bound, we are able to show that our simulation is optimal.

Compressed postscript
Compressed dvi