From Two-Way to One-Way Finite State Transducers

Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier +1

Any two-way finite state automaton is equivalent to some one-way finite state automaton. This well-known result, shown by Rabin and Scott and independently by Shepherdson, states t…