User: Guest  Login
Original title:
Linear Tree Transducers 
Original subtitle:
From Equivalence to Balancedness 
Translated title:
Lineare Baumübersetzer 
Translated subtitle:
Von Äquivalenz zu Balanciertheit 
Year:
2020 
Document type:
Dissertation 
Institution:
Fakultät für Informatik 
Advisor:
Seidl, Helmut (Prof. Dr.) 
Referee:
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...    »
 
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...    »
 
Oral examination:
27.11.2020 
File size:
852791 bytes 
Pages:
120 
Last change:
26.01.2021