5 papers
Deterministic regular functions of infinite words
Olivier Carton, Gaëtan Douéneau-Tabot, Emmanuel Filiot +1
Regular functions of infinite words are (partial) functions realized by deterministic two-way transducers with infinite look-ahead. Equivalently, Alur et. al. have shown that they…
Pebble minimization: the last theorems
Gaëtan Douéneau-Tabot
Pebble transducers are nested two-way transducers which can drop marks (named "pebbles") on their input word. Such machines can compute functions whose output size is polynomial in…
Continuous rational functions are deterministic regular
Olivier Carton, Gaëtan Douéneau-Tabot
A word-to-word function is rational if it can be realized by a non-deterministic one-way transducer. Over finite words, it is a classical result that any rational function is regul…
Hiding pebbles when the output alphabet is unary
Gaëtan Douéneau-Tabot
Pebble transducers are nested two-way transducers which can drop marks (named "pebbles") on their input word. Blind transducers have been introduced by Nguyên et al. as a subclass…
Pebble transducers with unary output
Gaëtan Douéneau-Tabot
Bojańczyk recently initiated an intensive study of deterministic pebble transducers, which are two-way automata that can drop marks (named "pebbles") on their input word, and produ…