Definability problems for tree transducers
Date Issued
2024-11-25
Author(s)
Supervisors
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.
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.
Subjects
Tree Transducer
;
Definability
Institution
Type
Dissertation
Language
English
File(s)![Thumbnail Image]()
Loading...
Name
Definability problems for tree transducers_dissertation_martin_vu.pdf
Size
1.46 MB
Format
Adobe PDF
Checksum
(MD5):66c1eaacc7b8720eb5a5a5cc50bcff1b