Two-Way Finite Automata: Old and Recent Results
Giovanni Pighizzini · Fundamenta Informaticae · 2013
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