Two-Way Automata Simulations and Unary Languages

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 unary case, namely for automata with a one-letter input alphabet, the question can be restricted to studying the cost of simulating quasi sweeping two-way nondeterministic automata accepting 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