Search

• < Previous
• 1
• Next >

---

One-way definability of two-way word transducers

Félix Baschenis ; Olivier Gauwin ; Anca Muscholl ; Gabriele Puppis.

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 words to words. It was shown in 2013 that it is decidable if such a transduction can be implemented by some one-way&nbsp;[&hellip;]

---

Streamability of nested word transductions

Emmanuel Filiot ; Olivier Gauwin ; Pierre-Alain Reynier ; Frédéric Servais.

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 height bounded memory (HBM) if it can be evaluated with a memory that depends only on the size of T and on the height&nbsp;[&hellip;]

---

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-visible alphabet) using a common deterministic transition graph, such that each language is associated with an initial&nbsp;[&hellip;]

---

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 subclass of aperiodic languages is defined by: counter-free automata, star-free expressions, aperiodic (finite)&nbsp;[&hellip;]

---