13 citations · 17 across the 6 of their papers we have counts for
4 papers · 1 filter
Streamability of nested word transductions
Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier +1
We consider the problem of evaluating in streaming (i.e., in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be…
One-way definability of two-way word transducers
Félix Baschenis, Olivier Gauwin, Anca Muscholl +1
Functional transductions realized by two-way transducers (or, equally, by streaming transducers or MSO transductions) are the natural and standard notion of "regular" mappings from…
Logical and Algebraic Characterizations of Rational Transductions
Emmanuel Filiot, Olivier Gauwin, Nathan Lhote
Rational word languages can be defined by several equivalent means: finite state automata, rational expressions, finite congruences, or monadic second-order (MSO) logic. The robust…
Untwisting two-way transducers in elementary time
Félix Baschenis, Olivier Gauwin, Anca Muscholl +1
Functional transductions realized by two-way transducers (equivalently, by streaming transducers and by MSO transductions) are the natural and standard notion of "regular" mappings…