2 papers
cs.FL2025
Reversible Pebble Transducers
Luc Dartois, Paul Gastin, L. Germerie Guizouarn +1
Deterministic two-way transducers with pebbles (aka pebble transducers) capture the class of polyregular functions, which extend the string-to-string regular functions allowing pol…
cs.FL2024
Reversible Transducers over Infinite Words
Luc Dartois, Paul Gastin, Loïc Germerie Guizouarn +2
Deterministic two-way transducers capture the class of regular functions. The efficiency of composing two-way transducers has a direct implication in algorithmic problems related t…