|
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 = {Two-Way Automata Simulations and Unary Languages},
journal = jalc,
year = 2000,
volume = 5,
number = 3,
pages = {287--300},
keywords = {unary automata, cyclic automata, two-way 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
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.}
}