Tree transducers are an expressive formalism for reasoning about data in a tree structure. Practical applications range from XSLT-like document transformations to translations of natural languages. Important problems for transducers are to decide whether two transducers are equivalent, to construct normal forms, give semantic characterizations, and type checking, i.e., to check whether the produced outputs satisfy given structural constraints. This thesis addresses these problems for important classes of tree transducers. We provide constructive solutions and also identify classes of transducers for which these algorithms run in polynomial time. Concerning semantic characterization of deterministic bottom-up tree transducers, we provide a Myhill-Nerode theorem. Concerning normalization and testing for equivalence, we show that for every deterministic bottom-up tree transducer, a unique equivalent transducer can be constructed which is minimal. For a deterministic bottom-up transducer where every state produces either none or infinitely many outputs, the minimal transducer can be constructed in polynomial time. In general, type checking of tree walking transducers is expensive: already for simple top-down tree transducers it is known to be EXPTIME-complete. Using forward type inference it is shown that type checking can be performed in polynomial time, if (1) the output type is specified by a deterministic tree automaton and (2) the tree walking transducer visits every input node only a bounded number of times. If the transducer is additionally equipped with accumulating call-by-value parameters, then the complexity of type checking also depends (exponentially) on the number of such parameters. For this case a fast approximative type checking algorithm is presented, based on context-free tree grammars. Finally, the approach is generalized from trees to forest walking transducers which additionally support concatenation as a built-in output operation.      «

Tree transducers are an expressive formalism for reasoning about data in a tree structure. Practical applications range from XSLT-like document transformations to translations of natural languages. Important problems for transducers are to decide whether two transducers are equivalent, to construct normal forms, give semantic characterizations, and type checking, i.e., to check whether the produced outputs satisfy given structural constraints. This thesis addresses these problems for important c...     »

Baumübersetzer sind ein ausdrucksstarker Formalismus um Daten, die in Baumstrukturen vorliegen, zu analysieren. Praktische Anwendungen reichen von XSLT-artigen Dokumentumstrukturierungen zu Übersetzungen natürlicher Sprache. Bedeutende Problemstellungen für Übersetzer sind zu entscheiden, ob zwei Übersetzer äquivalent sind, eine Normalform konstruiert werden kann, es eine semantische Charakterisierung gibt und Typüberprüfung, d.h., zu überprüfen, ob die erzeugten Ausgaben gegebene strukturelle Bedingungen erfüllen. Diese Dissertation befasst sich mit diesen Fragen für wesentliche Baumübersetzerklassen. Wir stellen konstruktive Lösungen bereit und identifizieren Übersetzerklassen, für die diese Algorithmen nur polynomielle Zeit benötigen. Zur semantischen Charakterisierung von deterministischen Aufwärts-Baumübersetzern (deterministic bottom-up tree transducers) präsentieren wir ein Myhill-Nerode Theorem. Bezüglich Normalisierung und Äquivalenztest zeigen wir, dass für jeden solchen Übersetzer ein eindeutiger äquivalenter Übersetzer konstruiert werden kann, der minimal ist. Wenn jeder Zustand eines deterministischen Aufwärts-Baumübersetzers entweder keine oder unendlich viele Ausgaben produziert, kann der minimale Übersetzer in polynomieller Zeit konstruiert werden. Im Allgemeinen ist Typüberprüfung von Zwei-Wege-Baumübersetzern (tree walking transducers) extrem aufwändig. Es ist bekannt, dass dieses Problem bereits für einfache Abwärts-Baumübersetzer (top-down tree transducers) EXPTIME-vollständig ist. Basierend auf vorwärtsgerichteter Typinferenz zeigen wir, dass man Typüberprüfung in polynomieller Zeit durchführen kann, wenn (1) der Ausgabetyp mittels eines deterministischen Automaten gegeben ist und (2) der Zwei-Wege-Baumübersetzer jeden Knoten eines Eingabebaums höchstens begrenzt oft besucht. Wenn der Baumübersetzer zusätzlich mit Wertparametern (call-by-value) ausgestattet ist, hängt die Komplexität außerdem (exponentiell) von der Anzahl der Parameter ab. In diesem Fall wird ein schneller approximativer Typüberprüfungsalgorithmus präsentiert, der auf kontextfreien Baumgrammatiken basiert. Zum Schluß wird dieser Ansatz von Bäumen auf Zwei-Wege-Waldübersetzer verallgemeinert. Diese Übersetzer erlauben zusätzlich Konkatenation als Operation auf Ausgabebäumen.     «

Baumübersetzer sind ein ausdrucksstarker Formalismus um Daten, die in Baumstrukturen vorliegen, zu analysieren. Praktische Anwendungen reichen von XSLT-artigen Dokumentumstrukturierungen zu Übersetzungen natürlicher Sprache. Bedeutende Problemstellungen für Übersetzer sind zu entscheiden, ob zwei Übersetzer äquivalent sind, eine Normalform konstruiert werden kann, es eine semantische Charakterisierung gibt und Typüberprüfung, d.h., zu überprüfen, ob die erzeugten Ausgaben gegebene strukturelle B...     »