Conference paper with F. Baschenis, O. Gauwin and A. Muscholl
One-way definability of sweeping transducers
In Proceedings of the 35th IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
Leibniz International Proceedings in Informatics (LIPIcs), volume 45, pages 178-191, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Pdf Bibtex Slides Abstract
Two-way finite-state transducers on words are strictly more expressive than one-way transducers. It has been shown recently how to decide if a two-way functional transducer has an equivalent one-way transducer, and the complexity of the algorithm is non-elementary. We propose an alternative and simpler characterization for sweeping functional transducers, namely, for transducers that can only reverse their head direction at the extremities of the input. Our algorithm works in 2EXPSPACE and, in the positive case, produces an equivalent one-way transducer of doubly exponential size. We also show that the bound on the size of the transducer is tight, and that the one-way definability problem is undecidable for (sweeping) non-functional transducers.