Definability problems for tree transducers

Abstract

In dieser Arbeit betrachten wir Definierbarkeitsprobleme für ‘Tree Transducer’, das heißt Maschinen, welche Bäume als Eingabe nehmen und diese zu Ausgabebäumen übersetzen. Definierbarkeitsprobleme sind Fragen der folgenden Art: Ist es für einen gegebenen Tree Transducer T aus einer Klasse C entscheidbar, ob es einen äquivalenten Tree Transducer aus der Klasse C ′ gibt und falls ja, können wir solch einen Tree Transducer konstruieren? Falls die Antwort zu dieser Frage ‘ja’ ist, sagen wir, dass die Klasse C ′ innerhalb der Klasse C definierbar ist. Typischerweise ist die Klasse C ′ eine strikte Unterklasse von C. Im Speziellen liegt der Schwerpunkt in dieser Arbeit auf der Klasse der Top-Down Tree Transducer und der Klasse der Attributed Tree Transducer.