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