4 papers
Hamming distance between finite transducers
Luc Dartois, Pierre-Cyrille Héam, Ismaël Jecker +1
We study bounded deviation of non-deterministic finite transducers under the Hamming distance: the bounded comparison problem asks, given two transducers and , wh…
Tree transducers of linear size-to-height increase (and the additive conjunction of linear logic)
Luc Dartois, Lê Thà nh Dũng Nguyên, Charles Peyrat
We investigate a natural generalization to trees of Hennie machines, a known automaton model for regular string functions. Tree-to-tree Hennie machines are tree-walking tree transd…
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…
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…