Aperiodic Two-way Transducers and FO-Transductions
Olivier Carton, Luc Dartois · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2015
Deterministic two-way transducers on finite words have been shown by Engelfriet and Hoogeboom to have the same expressive power as MSO-transductions. We introduce a notion of aperiodicity for these transducers and we show that aperiodic transducers correspond exactly to FO-transductions. This lifts to transducers the classical equivalence for languages between FO-definability, recognition by aperiodic monoids and acceptance by counter-free automata.