Shape Preserving Tree Transducers

2025/06/27 by Gallot, Paul, Maneth, Sebastian
#68U99 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2506.22047

Abstract

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. Moreover, if a transducer is shape preserving, then it can be brought into a particular normal form, where every input node creates exactly one output node.

Citations

• Deciding Linear Height and Linear Size-to-Height Increase for Macro Tree Transducers
• Definability Results for Top-Down Tree Transducers
• Linear Bounded Composition of Tree-Walking Tree Transducers: Linear Size\n Increase and Complexity
• From Two-Way to One-Way Finite State Transducers
• The Equivalence Problem for Deterministic MSO Tree Transducers is Decidable

Related

• How to decide Functionality of Compositions of Top-Down Tree Transducers
• Look-Ahead Removal for Top-Down Tree Transducers
• Two or three things I know about tree transducers
• Definability Results for Top-Down Tree Transducers
• Deciding Linear Height and Linear Size-to-Height Increase for Macro Tree Transducers