Two--way Automata Simulations and Unary Languages

Carlo Mereghetti

Dipartimento di Informatica, Sistemistica e Comunicazione
Università degli Studi di Milano -- Bicocca
via Bicocca degli Arcimboldi 8 -- 20126 Milano, Italy.

Giovanni Pighizzini

Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy
One of the main problems in automata theory is evaluating the cost, in terms of states, of the optimal simulation of two--way (or also one--way) nondeterministic by two--way deterministic automata. The question, which was proposed in 1978 by W. Sakoda and M. Sipser, is still open. In this paper, we aim to give some contributions to the investigation of this problem. We show that in the {\em unary} case, namely for automata with a one--letter input alphabet, the question can be restricted to studying the cost of simulating \emph{quasi sweeping} two--way nondeterministic automata accepting \emph{cyclic languages} by two--way deterministic automata. Next, we prove a tight lower bound on the number of states of two--way deterministic, nondeterministic, and quasi sweeping automata accepting unary languages. 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 simulation, which is shown to be optimal, improves the known quadratic simulation for unary regular languages.