Two-way automata simulations and unary languages

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 {\sc W. Sakoda} and {\sc 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 \emph{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