2026-07-26T02:16:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12541 2024-03-06T10:50:24Z ddc:004 open_access

When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic? Maneth, Sebastian Seidl, Helmut Top-Down Tree Transducers Earliest Transformation Linear Transducers Uniform-copying Transucers Removal of Look-ahead Removal of Inspection We consider two natural subclasses of deterministic top-down tree-to-tree transducers, namely, linear and uniform-copying transducers. For both classes we show that it is decidable whether the translation of a transducer with look-ahead can be realized by a transducer without look-ahead. The transducers constructed in this way, may still make use of inspection, i.e., have an additional tree automaton restricting the domain. We provide a second procedure which decides whether inspection can be removed and if so, constructs an equivalent transducer without inspection. The construction relies on a fixpoint algorithm that determines inspection requirements and on dedicated earliest normal forms for linear as well as uniform-copying transducers which can be constructed in polynomial time. As a consequence, equivalence of these transducers can be decided in polynomial time. Applying these results to deterministic bottom-up transducers, we obtain that it is decidable whether or not their translations can be realized by deterministic uniform-copying top-down transducers without look-ahead (but with inspection) - or without both look-ahead and inspection. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sebastian Maneth and Helmut Seidl 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.134 urn:nbn:de:0030-drops-125416 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.134 eng https://creativecommons.org/licenses/by/3.0/legalcode