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...     »

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...     »