Two--way Automata Simulations and Unary Languages

<TITLE>Two--way Automata Simulations and Unary
                                        Languages</TITLE>

<H2 ALIGN="CENTER">Two--way Automata Simulations and Unary
                                        Languages</H2>

<H4 ALIGN="CENTER">Carlo Mereghetti</H4>

<H6 ALIGN="CENTER">Dipartimento di Informatica, Sistemistica e 
Comunicazione<BR>
Universit&agrave; degli Studi di Milano -- Bicocca<BR>
         via Bicocca degli Arcimboldi 8 -- 20126 Milano, Italy.</H6>
		<BR>
		
<H4 ALIGN="CENTER">Giovanni Pighizzini</H4>

<H6 ALIGN="CENTER">Dipartimento di  Scienze dell'Informazione<BR>
Universit&agrave; degli Studi di Milano<BR>
via Comelico 39 -- 20135  Milano, Italy</H6>

<H5 ALIGN="CENTER">Abstract</H5>

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.