Seidl, Helmut (Prof. Dr.); Maneth, Sebastian (Prof. Dr.)
Language:
en
Subject group:
DAT Datenverarbeitung, Informatik
TUM classification:
DAT 500d
Abstract:
This thesis studies two decision problems on linear tree transducers with serialized output -- equivalence and balancedness. We show that equivalence of linear tree transducers with output in the free group is decidable in polynomial time. For the second decision problem -- balancedness -- the output is interpreted over the involutive monoid. We consider 2-copy tree transducers (2-TWs) which call in their starting axiom two linear tree transducers on the same input and show that balancedness of 2-TWs is decidable in polynomial time.
«
This thesis studies two decision problems on linear tree transducers with serialized output -- equivalence and balancedness. We show that equivalence of linear tree transducers with output in the free group is decidable in polynomial time. For the second decision problem -- balancedness -- the output is interpreted over the involutive monoid. We consider 2-copy tree transducers (2-TWs) which call in their starting axiom two linear tree transducers on the same input and show that balancedness of...
»
Translated abstract:
Diese Arbeit untersucht zwei Entscheidungsprobleme über lineare Baumübersetzer -- Äquivalenz und Balanciertheit. Wir zeigen, dass die Äquivalenz von linearen Baumübersetzern mit Ausgabe in der freien Gruppe in polynomieller Zeit entscheidbar ist. Für das zweite Entscheidungsproblem -- Balanciertheit -- wird die Ausgabe über einem Monoid mit Involution interpretiert. Wir betrachten Baumübersetzer mit zwei Kopien (2-TWs), die in ihrer Startregel zwei lineare Baumübersetzer mit der gleichen Eingabe aufrufen und zeigen, dass Balanciertheit von 2-TWs in polynomieller Zeit entschieden werden kann.
«
Diese Arbeit untersucht zwei Entscheidungsprobleme über lineare Baumübersetzer -- Äquivalenz und Balanciertheit. Wir zeigen, dass die Äquivalenz von linearen Baumübersetzern mit Ausgabe in der freien Gruppe in polynomieller Zeit entscheidbar ist. Für das zweite Entscheidungsproblem -- Balanciertheit -- wird die Ausgabe über einem Monoid mit Involution interpretiert. Wir betrachten Baumübersetzer mit zwei Kopien (2-TWs), die in ihrer Startregel zwei lineare Baumübersetzer mit der gleichen Eingabe...
»