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…