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 
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 t...    »
 
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 Zwe...    »
 
Oral examination:
27.07.2011 
File size:
3219126 bytes 
Pages:
219 
Last change:
29.08.2011