Affine λ-transducers with additive branching
Lê Thành Dũng (Tito) Nguyễn
LIS, Aix-Marseille
https://nguyentito.eu/
Date(s) : 19/03/2026 iCal
11h00 - 12h30
This talk will cover the equivalence in expressive power between two models of computation for tree-to-tree functions:
- tree-to-tree Hennie machines, a variant of linear-time Turing machines
- higher-order transducers subject to a suitable affine typing condition
This equivalence suggests that these devices define a canonical function class. There are two motivations for studying this class:
- its linear size-to-height increase property, cf. Dartois, N. & Peyrat https://nguyentito.eu/lshi.pdf
- recently discovered connections with MSO set interpretations on strings, cf. Colcombet, Lhote & Ohlmann https://arxiv.org/abs/2602.21019
Catégories
