Non-determinism and walking mechanisms were considered already at the very beginning of automata theory. I will survey a few results connecting models of automata and transducers enhanced with non-determinism and two-wayness.

A classical result by Rabin and Scott shows that deterministic finite state automata are as expressive as their non-deterministic and two-way counterparts. The translation from two-way automata to one-way automata is easily seen to imply an exponential blowup in the worst case, even when one maps deterministic two-way models to non-deterministic one-way models. The converse translation, which is based on the subset construction and maps non-deterministic one-way automata to deterministic ones, also implies an exponential blowup. This latter translation, however, is not known to be optimal when one aims at removing non-determinism by possibly introducing two-wayness. In particular, the question of whether the exponential blowup is unavoidable in transforming non-determinism to two-wayness is open.

When one turns to models of transducers, some translations are not anymore possible. For example, one-way transducers (even those that exploit functional non-determinism) are easily seen to be less powerful than two-way transducers (even input-deterministic ones). A natural problem thus arises that amounts at characterizing the two-way transductions that can be implemented by one-way functional transducers. The latter problem was solved in recent paper by Filiot, Gauwin, Reynier, and Servais – however, some questions related to complexity remains open. Another interesting, but older, result by Hopcroft shows that functional non-determinism can be removed from two-way transducers, at the cost of an exponential blow-up. A similar transformation can be used to prove that two-way transducers are closed under functional composition.