
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik


@article{jalc050309,
author = {Mereghetti, Carlo and Pighizzini, Giovanni},
title = {TwoWay Automata Simulations and Unary Languages},
journal = jalc,
year = 2000,
volume = 5,
number = 3,
pages = {287300},
keywords = {unary automata, cyclic automata, twoway automata,
descriptional complexity},
abstract = {One of the main problems in automata theory is evaluating
the cost, in terms of states, of the optimal simulation of
twoway (or also oneway) nondeterministic by twoway
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 oneletter
input alphabet, the question can be restricted to studying
the cost of simulating \emph{quasi sweeping} twoway
nondeterministic automata accepting \emph{cyclic languages}
by twoway deterministic automata. Next, we prove a tight
lower bound on the number of states of twoway deterministic,
nondeterministic, and quasi sweeping automata accepting unary
languages. We also show that any oneway nondeterministic
automaton accepting a unary cyclic language can be simulated
by a twoway 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.}
}