2 papers
cs.FL2026
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…
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…