The notion of two-way automata was introduced at the very beginning of automata theory. In 1959, Rabin and Scott and, independently, Shepherdson, proved that these models, both in the deterministic and in the nondeterministic versions, have the same power of one-way automata, namely, they characterize the class of regular languages. In 1978, Sakoda and Sipser posed the question of the costs, in the number of the states, of the simulations of one-way and two-way non-deterministic automata by two-way deterministic automata. They conjectured that these costs are exponential. In spite of all attempts to solve it, this question is still open. In the last ten years the problem of Sakoda and Sipser was widely reconsidered and many new results related to it have been obtained. In this work we discuss some of them. In particular, we focus on the restriction to the unary case, namely the case of automata defined over the one letter input alphabet, and on the connections with open questions in space complexity.
Two-way finite automata: Old and recent results / G. Pighizzini. - In: FUNDAMENTA INFORMATICAE. - ISSN 0169-2968. - 126:2-3(2013), pp. 225-246. [10.3233/FI-2013-879]
Two-way finite automata: Old and recent results
G. Pighizzini
2013
Abstract
The notion of two-way automata was introduced at the very beginning of automata theory. In 1959, Rabin and Scott and, independently, Shepherdson, proved that these models, both in the deterministic and in the nondeterministic versions, have the same power of one-way automata, namely, they characterize the class of regular languages. In 1978, Sakoda and Sipser posed the question of the costs, in the number of the states, of the simulations of one-way and two-way non-deterministic automata by two-way deterministic automata. They conjectured that these costs are exponential. In spite of all attempts to solve it, this question is still open. In the last ten years the problem of Sakoda and Sipser was widely reconsidered and many new results related to it have been obtained. In this work we discuss some of them. In particular, we focus on the restriction to the unary case, namely the case of automata defined over the one letter input alphabet, and on the connections with open questions in space complexity.File | Dimensione | Formato | |
---|---|---|---|
fi_2013_126-2,3_FI126(2-3)06.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
154.88 kB
Formato
Adobe PDF
|
154.88 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.