Benutzer: Gast  Login
Originaltitel:
Linear Tree Transducers
Originaluntertitel:
From Equivalence to Balancedness
Übersetzter Titel:
Lineare Baumübersetzer
Übersetzter Untertitel:
Von Äquivalenz zu Balanciertheit
Autor:
Löbel, Raphaela
Jahr:
2020
Dokumenttyp:
Dissertation
Fakultät/School:
Fakultät für Informatik
Betreuer:
Seidl, Helmut (Prof. Dr.)
Gutachter:
Seidl, Helmut (Prof. Dr.); Maneth, Sebastian (Prof. Dr.)
Sprache:
en
Fachgebiet:
DAT Datenverarbeitung, Informatik
TU-Systematik:
DAT 500d
Kurzfassung:
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...     »
Übersetzte Kurzfassung:
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...     »
WWW:
https://mediatum.ub.tum.de/?id=1552125
Eingereicht am:
06.07.2020
Mündliche Prüfung:
27.11.2020
Dateigröße:
852791 bytes
Seiten:
120
Urn (Zitierfähige URL):
https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20201127-1552125-1-5
Letzte Änderung:
26.01.2021
 BibTeX