2012/08/13 by Giovanni Pighizzini
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Artificial intelligence #Automata theory #Automaton #Class (philosophy) #Computer science #Continuous spatial automaton #DNA and Biological Computing #Discrete mathematics #Expressive power #Focus (optics) #Logic, programming, and type systems #Mathematics #Nested word #Nondeterministic algorithm #Nondeterministic finite automaton #Quantum finite automata #Theoretical computer science #Unary operation #cs.CC #cs.FL #semigroups and automata theory #ω-automaton
paper · pdf · doi:10.4204/eptcs.90.1
published as EPTCS 90, 2012, pp. 3-20 · In Proceedings AUTOMATA&JAC 2012, arXiv:1208.2498
openalex publication_date 2012/08/13 · arxiv created 2012/08/14 · arxiv updated 2012/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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 cost, in the number of the states, of the simulation of one-way and two-way nondeterministic 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 and on the connections with open questions in space complexity.