1 citations · 1 across the 3 of their papers we have counts for
Showing cs.FLShow all
3 papers · 1 filter
cs.FL2025
Shape Preserving Tree Transducers
Paul Gallot, Sebastian Maneth
It is shown that shape preservation is decidable for top-down tree transducers, bottom-up tree transducers, and for compositions of total deterministic macro tree transducers. More…
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.FL2023
Deciding Linear Height and Linear Size-to-Height Increase for Macro Tree Transducers
Paul Gallot, Sebastian Maneth, Keisuke Nakano +1
We present a novel normal form for (total deterministic) macro tree transducers (mtts), called depth proper normal form. If an mtt is in this normal form, then it is guaranteed tha…