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

CREATORLuc Dartois, Lê Thành Dũng (Tito) Nguyễn, Charles Peyrat
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE189 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.03928

Browse the full library · About the Tower of Babel