Unary automata simulations and cyclic languages

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.