13 citations · 17 across the 6 of their papers we have counts for
6 papers · 1 filter
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…
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…