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 transducers can be performed in polynomial time, if the output type is specified by a deterministic tree automaton and the transducer visits every input node only a bounded number of times. Finally, the approach is generalized to transducers with accumulating parameters and to forest walking transducers.     «

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...     »

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-Wege-Baumübersetzern in polynomieller Zeit durchführen kann, wenn der Ausgabetyp durch einen deterministischen Automaten gegeben ist und der Übersetzer jeden Knoten eines Baums nur begrenzt oft besucht. Dieser Ansatz wird auf Übersetzer mit Wertparametern und Zwei-Wege-Waldübersetzer verallgemeinert.     «

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-...     »