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
Abstract
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.