Conference paper with F. Baschenis,O. Gauwin, A. Muscholl, and G. Puppis (To appear) Untwisting two-way transducers in elementary time In Proceedings of the 32nd Annual IEEE Symposium on Logic in Computer Science (LICS) ACM PdfAbstract
Functional transductions realized by two-way transducers (equivalently, by streaming transducers and by MSOtransductions) are the natural and standard notion of “regular” mappings from words to words. It was shown recently (LICS’13) that it is decidable if such a transduction can be implemented by some one-way transducer, but the given algorithm has non-elementary complexity. We provide an algorithm of different flavor solving the above question, that has double exponential space complexity. We further apply our technique to decide whether the transduction realized by a two-way transducer can be implemented by a sweeping transducer, with either known or unknown number of passes.
Conference paper with F. Baschenis, O. Gauwin and A. Muscholl Minimizing resources of sweeping and streaming string transducers In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP) Leibniz International Proceedings in Informatics (LIPIcs), volume 55, pages 1-14, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik PdfBibtexSlidesAbstract
We consider minimization problems for natural parameters of word transducers: the number of passes performed by two-way transducers and the number of registers used by streaming transducers. We show how to compute in ExpSpace the minimum number of passes needed to implement a transduction given as sweeping transducer, and we provide effective constructions of transducers of (worst-case optimal) doubly exponential size. We then consider streaming transducers where concatenations of registers are forbidden in the register updates. Based on a correspondence between the number of passes of sweeping transducers and the number of registers of equivalent concatenation-free streaming transducers, we derive a minimization procedure for the number of registers of concatenation-free streaming transducers.
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 PdfBibtexSlidesAbstract
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.
Mathematics and computer science student at ENS Cachan (2009-2014)
Agregation of Mathematics (2013)
LMFI Master thesis at LIAFA, France under the supervision of Amélie Gheerbrant (2014)