Theorie der Gewichteten Baumautomaten im Wintersemester 2022/23

Einführung

In vielen Bereichen der Informatik werden Bäume verwendet, um Daten zu strukturieren und hierarchische Abhängigkeiten zwischen einzelnen Daten darzustellen; z.B. kann die Struktur eines Satzes einer natürlichen Sprache als Baum (parse tree) dargestellt werden. Deshalb ist es von allgemeinem Interesse, Algorithmen bereitzustellen, welche Bäume auf bestimmte Eigenschaften untersuchen, Bäume durch Zuordnung von Gewichten bewerten oder Bäume in andere Bäume überführen. In dieser Vorlesung werden wir die Theorie der gewichteten Baumautomaten behandeln.

Baumautomaten sind formale Modelle für Algorithmen zur Beschreibung von Mengen von Bäumen. In dieser Vorlesung werden wir ihre grundlegenden Definitionen auf theoretischem Niveau einführen sowie verschiedene ihrer formalen Eigenschaften kennenlernen und beweisen, z.B. Resultate zur Charakterisierung und Determinisierung.

Termine

Vorlesung:

• Montag, 3. DS (11:10 Uhr bis 12:40 Uhr), APB/E006/U
• Donnerstag, 2. DS (9:20 Uhr bis 10:50 Uhr), APB/E006/U

Übung: Donnerstag, 3. DS (11:10 Uhr bis 12:40 Uhr), APB/E006/U

Materialien

Hinweis: Sie können sich anhand des vorherigen Durchlaufs einen Überblick verschaffen.

Der Download der Vorlesungsmaterialien ist auf das Netzwerk der TU Dresden beschränkt. Für Downloads aus anderen Netzen können Sie den VPN-Zugang des ZIHs benutzen.

Vorlesung

An dieser Stelle werden wöchentlich Teile des Vorlesungsskripts erscheinen. Die dazugehörigen Referenzen finden Sie separat am Ende dieser Seite. Das Skript ist urheberrechtlich geschützt und darf nur für das persönliche Studium verwendet werden. Die Verbreitung ist untersagt.

Übung

An dieser Stelle werden im Verlauf des Semesters die Übungsblätter bereitgestellt. Aufgaben, die in der aufgeführten Woche nicht bearbeitet wurden, werden in der darauffolgenden Woche nachgeholt.

Literatur

1. Baader, F. and Nipkow, T. 1998. Term Rewriting and All That. Cambridge University Press.
2. Brainerd, W.S. 1969. Tree Generating Regular Systems. Information and Control 14, 2, 217–231. [doi]
3. Engelfriet, J. 1975. Tree Automata and Tree Grammars. Aarhus University. [arXiv]
4. Engelfriet, J. 1975. Bottom-up and top-down tree transformations—a comparison. Mathematical systems theory 9, 2, 198–231. [doi]
5. Fülöp, Z. and Vogler, H. 1998. Syntax-Directed Semantics: Formal Models Based on Tree Transducers. Springer Berlin Heidelberg. [doi]
6. Grätzer, G. 1968. Universal Algebra. Van Nostrand, Princeton (NJ). [doi]
7. Grätzer, G. 1979. General Lattice Theory. Birkhäuser Verlag.
8. Gécseg, F. and Steinby, M. 1984. Tree Automata. Akadémiai Kiadó. [url]
9. Gécseg, F. and Steinby, M. 1997. Tree Languages. In: G. Rozenberg and A. Salomaa, eds., Handbook of Formal Languages. Springer Berlin Heidelberg, 1–68. [doi]
10. Thatcher, J.W. 1967. Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. Journal of Computer and System Sciences 1, 4, 317–322. [doi]

Kontakt

• Prof. Dr.-Ing. habil. Dr. h.c./Univ. Szeged
  Heiko Vogler
  Tel.: +49 (0) 351 463-38232