13 citations · 17 across the 6 of their papers we have counts for
7 papers
Minimization of visibly pushdown automata is NP-complete
Olivier Gauwin, Anca Muscholl, Michael Raskin
We show that the minimization of visibly pushdown automata is NP-complete. This result is obtained by introducing immersions, that recognize multiple languages (over a usual, non-v…
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…
From Two-Way to One-Way Finite State Transducers
Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier +1
Any two-way finite state automaton is equivalent to some one-way finite state automaton. This well-known result, shown by Rabin and Scott and independently by Shepherdson, states t…
Visibly pushdown automata on trees: universality and u-universality
Véronique Bruyère, Marc Ducobu, Olivier Gauwin
An automaton is universal if it accepts every possible input. We study the notion of u-universality, which asserts that the automaton accepts every input starting with u. Universal…