User: Guest  Login
Original title:
On Normalization and Type Checking for Tree Transducers
Translated title:
Über Normalisierung und Typüberprüfung für Baumübersetzer
Author:
Friese, Sylvia
Year:
2011
Document type:
Dissertation
Institution:
Fakultät für Informatik
Advisor:
Seidl, Helmut (Prof. Dr.)
Referee:
Schulz, Klaus U. (Prof. Dr.); Seidl, Helmut (Prof. Dr.)
Language:
en
Subject group:
DAT Datenverarbeitung, Informatik
Keywords:
Tree Transducer, Myhill-Nerode Theorem, Normalization, Type Checking
Translated keywords:
Baumübersetzer, Myhill-Nerode, Normalisierung, Typüberprüfung
Abstract:
Tree transducers are an expressive formalism for reasoning about tree-structured data. Practical applications range from XSLT-like document transformations to translations of natural languages. We show that for every deterministic bottom-up tree transducer, a unique equivalent minimal transducer can be constructed - in polynomial time if every state of the transducer produces either none or infinitely many outputs. Using forward type inference it is shown that type checking of tree walking tra...    »
Translated abstract:
Baumübersetzer sind ein ausdrucksstarker Formalismus zur Analyse strukturierter Daten. Praktische Anwendungen reichen von XSLT-artigen Übersetzungen zu Übersetzungen natürlicher Sprache. Wir zeigen, dass für jeden deterministischen Aufwärts-Baumübersetzer ein eindeutiger äquivalenter minimaler Übersetzer konstruiert werden kann - in polynomieller Zeit, wenn jeder Zustand des Übersetzers entweder keine oder unendlich viele Ausgaben produziert. Zudem zeigen wir, dass man Typüberprüfung von Zwei-...    »
WWW:
https://mediatum.ub.tum.de/?id=1078090
Date of submission:
24.03.2011
Oral examination:
27.07.2011
File size:
3219126 bytes
Pages:
219
Urn (citeable URL):
https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20110727-1078090-1-9
Last change:
29.08.2011
 BibTeX