Theorie der Gewichteten Baumautomaten im Wintersemester 2020/21

Diese Vorlesung beeinhaltet (und erweitert) den Stoff der Vorlesungen Gewichtete Baumautomaten WS19/20 und Formale Baumsprachen SoSe 2020. Aus diesem Grund kann nur eine dieser Vorlesungen geprüft werden.

Aktuelle Hinweise

Aufgrund von SARS-CoV-2 und dem damit verbundenen eingeschränkten Präsenzbetrieb an der TU Dresden verfahren wir wie folgt:

• Die Vorlesungen und Übungen beginnen mit dem verschobenen Semesterstart zum 26.10. und finden virtuell statt.
• Bitte schreiben Sie sich in den zugehörigen OPAL-Kurs ein.
• Zu den Vorlesungsterminen werden Folien mit Sprachaufzeichnungen online zur Verfügung gestellt.
• Die Übungsaufgaben werden wöchtlich online zur Verfügung gestellt. Lösungen können von den Studierenden digital abgegeben werden und werden von uns kommentiert. Nach einigen Tagen werden auch Musterlösungen online veröffentlicht.
• Weitere Maßnahmen und Anpassungen erfolgen entsprechend den Empfehlungen der Universitätsleitung.

Einführung

In vielen Gebieten der Informatik werden Bäume genutzt, um Daten zu strukturieren und hierarchische Abhängigkeiten zwischen Teildaten darzustellen. Zum Beispiel kann die Struktur eines Satzes einer natürlichen Sprache als Baum (parse tree) dargestellt werden. Deshalb besteht ein allgemeines Interesse an Algorithmen und Maschinen, welche Bäume auf bestimmte Eigenschaften untersuchen, Bäume durch Zuordnung eines Gewichts sortieren oder Bäume in andere Bäume transformieren. Hier werden wir Charakterisierungen der Klasse der regulären Baumsprachen besprechen. Bei der Verarbeitung natürlichen Sprache (natural language processing; nlp) ist es beispielsweise wichtig, zu bestimmen ob ein Satz unter Beachtung grammatikalischer Regeln wohl-strukturiert ist, oder mögliche Übersetzungen eines Satzes der einen Sprache in eine andere Sprache zu finden.

In dieser Lehrveranstaltung werden wir ihre grundlegenden Definitionen und Eigenschaften auf einem theoretischen Niveau betrachten, dabei aber die Anwendung für die Verarbeitung natürlicher Sprachen nicht aus den Augen verlieren.

Audioaufzeichnungen zur Vorlesung

Die Audiofolien sind urheberrechtlich geschützt und dürfen nur für das persönliche Studium verwendet werden. Die Verbreitung ist untersagt. Die Aufzeichnungen sind nur aus dem Netz der TU abrufbar, nutzen Sie ggf VPN.

• KW 44: Einführung, Preliminaries I
• KW 45: Preliminaries II, Preliminaries III
• KW 46: Basic model I, Basic model II
• KW 47: Basic model III, Basic model IV, Special cases I, Special cases II
• KW 48: Relationship semantics I, Relationship semantics II, Relationship semantics III
• KW 49: Support: Negative result
• KW 50: Support: Positive result 1 I, Support: Positive result 1 II, Support: Positive result 1 III
• KW 51: Support: Positive result 2 I, Support: Positive result 2 II, Support: Comparison
• KW 1: Normal forms I, Normal forms II, Normal forms III, Normal forms IV
• KW 2: Weighted regular tree grammars: Definition
• KW 3: Wrtg: Simplifications I, Wrtg: Simplifications II, Wrtg - Wta
• KW 4: Closure results I, Closure results II
• KW 5: Closure results III

Material

An dieser Stelle werden wöchentlich Teile des Vorlesungsskripts erscheinen. Die dazugehörigen Referenzen finden Sie separat am Ende der folgenden Liste. Das Skript ist urheberrechtlich geschützt und darf nur für das persönliche Studium verwendet werden. Die Verbreitung ist untersagt. Die Materialien sind nur aus dem Netz der TU abrufbar, nutzen Sie ggf VPN.

• Preliminaries
• Basic model
• Relationship semantics
• Support
• Normal forms
• Weighted regular tree grammars
• Closure results (aktualisiert am 11.03.)

Übungsaufgaben

Übungsaufgaben werden wöchentlich (jeweils freitags) an dieser Stelle veröffentlich. Sie haben die Möglichkeit, im OPAL-Kurs eigene Lösungen (bis zum darauffolgenden Freitag) einzureichen. Diese werden kommentiert und sind dann ebenfalls in OPAL abrufbar. Außerdem werden nach jedem Übungszyklus Musterlösungen hier veröffentlich.

• 1. Übungsblatt (KW 45), Musterlösung
• 2. Übungsblatt (KW 46), Musterlösung
• 3. Übungsblatt (KW 47), Musterlösung
• 4. Übungsblatt (KW 48), Musterlösung
• 5. Übungsblatt (KW 49), Musterlösung
• 6. Übungsblatt (KW 50), Musterlösung
• 7. Übungsblatt (KW 51), Musterlösung
• 8. Übungsblatt (KW 1), Musterlösung
• 9. Übungsblatt (KW 2), Musterlösung
• 10. Übungsblatt (KW 3), Musterlösung
• 11. Übungsblatt (KW 4), Musterlösung

Referenzen

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
• Dr. rer. nat. Luisa Herrmann
  Tel.: +49 (0) 351 463-38487