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
Abstract
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.
Download
Compressed postscript
Compressed dvi