2 citations · 4 across the 7 of their papers we have counts for
3 papers · 1 filter
Two-way automata and transducers with planar behaviours are aperiodic
Lê Thành Dũng Nguyên, Camille Noûs, Cécilia Pradic
We consider a notion of planarity for two-way finite automata and transducers, inspired by Temperley-Lieb monoids of planar diagrams. We show that this restriction captures star-fr…
Refutations of pebble minimization via output languages
Sandra Kiefer, Lê Thành Dũng Nguyên, Cécilia Pradic
Polyregular functions are the class of string-to-string functions definable by pebble transducers, an extension of finite-state automata with outputs and multiple two-way reading h…
Comparison-free polyregular functions
Lê Thành Dũng Tito Nguyên, Camille Noûs, Cécilia Pradic
This paper introduces a new automata-theoretic class of string-to-string functions with polynomial growth. Several equivalent definitions are provided: a machine model which is a r…