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
Two-way automata simulations and unary languages / C. Mereghetti, G. Pighizzini. - In: JOURNAL OF AUTOMATA, LANGUAGES AND COMBINATORICS. - ISSN 1430-189X. - 5:3(2000), pp. 287-300.
Two-way automata simulations and unary languages
C. MereghettiPrimo
;G. PighizziniUltimo
2000
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 languagesFile | Dimensione | Formato | |
---|---|---|---|
Mereghetti_two_2000.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
986.7 kB
Formato
Adobe PDF
|
986.7 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.