Tree transducers of linear size-to-height increase
Luc Dartois, Lê Thành Dũng (Tito) Nguyễn, Charles Peyrat · 2026
Read Tree transducers of linear size-to-height increase by Luc Dartois, Lê Thành Dũng (Tito) Nguyễn, Charles Peyrat (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03928.txt.
Description
Luc Dartois, Lê Thành Dũng Nguyên, and Charles Peyrat investigate tree-to-tree Hennie machines. These tree-walking transducers generalize a classical automaton for string functions. They may rewrite node labels under a bounded visit restriction. Unlike regular tree transducers, these machines compute a larger class of functions. They have linear size-to-height increase, a growth condition linking output height to input size.
The authors prove this function class sits between linear size-to-height macro tree transducers and MSO set interpretations. It is closed under precomposition and postcomposition by suitable macro tree transducers. It contains the whole composition hierarchy of linear-height-increase transducers. That hierarchy is strict. Finally, they give an alternative characterization through a lambda-calculus with linear types. There, additive tuples encode output trees. The characterization is proved equivalent via game semantics.
Catalog record
| CREATOR | Luc Dartois, Lê Thành Dũng (Tito) Nguyễn, Charles Peyrat |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 189 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.03928