Two-way vs one-way automata and transducers

Olivier Gauwin
LaBRI
Friday, 21 April, 2017 - 14:00
Salle P.OF2072
Usual finite state automata read their input rightwards. Shortly after their introduction, it has been shown that allowing to read the input in both directions (two-way) does not increase their expressive power. For this reason they did not deserve much attention ever since. However, when moving from automata to transducers, the situation changes: Two-way transducers are strictly more expressive than their one-way counterpart. In this talk we focus on the decision problem of deciding whether a two-way transducer has an equivalent one-way transducer. A first non-elementary procedure has been proposed in 2013, and two elementary algorithms emerged in the last months.