2026-07-25T01:47:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20281 2024-07-02T07:52:55Z ddc:004 open_access

Deciding Linear Height and Linear Size-To-Height Increase of Macro Tree Transducers Gallot, Paul Maneth, Sebastian Nakano, Keisuke Peyrat, Charles automata formal language theory macro tree transducer normal form 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 that each parameter of each state appears at arbitrary depths in the output trees of that state. Intuitively, if some parameter only appears at certain bounded depths in the output trees of a state, then this parameter can be eliminated by in-lining the corresponding output paths at each call site of that state. We use regular look-ahead in order to determine which of the paths should be in-lined. As a consequence of changing the look-ahead, a parameter that was previously appearing at unbounded depths, may be appearing at bounded depths for some new look-ahead; for this reason, our construction has to be iterated to obtain an mtt in depth-normal form. Using the normal form, we can decide whether the translation of an mtt has linear height increase or has linear size-to-height increase. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paul Gallot and Sebastian Maneth and Keisuke Nakano and Charles Peyrat 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.138 urn:nbn:de:0030-drops-202818 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.138 eng https://creativecommons.org/licenses/by/4.0/legalcode