TY - GEN
T1 - When is a bottom-up deterministic tree translation top-down deterministic?
AU - Maneth, Sebastian
AU - Seidl, Helmut
N1 - Publisher Copyright:
© Sebastian Maneth and Helmut Seidl; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).
PY - 2020/6/1
Y1 - 2020/6/1
N2 - 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.
AB - 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.
KW - Earliest Transformation
KW - Linear Transducers
KW - Removal of Inspection
KW - Removal of Look-ahead
KW - Top-Down Tree Transducers
KW - Uniform-copying Transucers
UR - http://www.scopus.com/inward/record.url?scp=85089340999&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2020.134
DO - 10.4230/LIPIcs.ICALP.2020.134
M3 - Conference contribution
AN - SCOPUS:85089340999
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
A2 - Czumaj, Artur
A2 - Dawar, Anuj
A2 - Merelli, Emanuela
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
Y2 - 8 July 2020 through 11 July 2020
ER -