5 citations · 19 across the 10 of their papers we have counts for
Showing cs.FLShow all
3 papers · 1 filter
cs.FL2025★ 1 cited
The structure of polynomial growth for tree automata/transducers and MSO set queries
Paul Gallot, Nathan Lhote, Lê Thành Dũng Nguyên
Given an -weighted tree automaton, we give a decision procedure for exponential vs polynomial growth (with respect to the input size) in quadratic time, and an algorith…
cs.FL2024
Slightly Non-Linear Higher-Order Tree Transducers
Lê Thành Dũng Nguyên, Gabriele Vanoni
We investigate the tree-to-tree functions computed by "affine -transducers": tree automata whose memory consists of an affine -term instead of a finite state. They can be see…
cs.FL2023★ 2 cited
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…