Formale Baumsprachen im Sommersemester 2020

Diese Vorlesung beeinhaltet (und erweitert) den Stoff der Vorlesung Gewichtete Baumautomaten WS19/20. Aus diesem Grund können nicht beide Vorlesungen geprüft werden.

Aktuelle Hinweise

Im Hinblick auf SARS-CoV-2 und die damit verbundene Verschiebung des Beginns der Präsenzveranstaltungen im Sommersemester 2020, verfahren wir wie folgt:

• Die Vorlesungen beginnen mit dem regulären Semesterstart zum 06.04. zunächst virtuell.
• Bitte schreiben Sie sich in den zugehörigen OPAL-Kurs ein.
• Prof. Vogler wird zu den Vorlesungsterminen Folien mit Sprachaufzeichnungen anfertigen und online zur Verfügung stellen.
• Die Übungsaufgaben werden zu den Übungsterminen 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 bzw. einen Übergang zum regulären Präsenzbetrieb 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 15: Einführung, Preliminaries I
• KW 16: Preliminaries II, Preliminaries III
• KW 17: Basic model I, Basic model II
• KW 18: Basic model III, Basic model IV
• KW 19: Special cases I, Special cases II
• KW 20+21: Relationship semantics I, Relationship semantics II, Relationship semantics III
• KW 22: Support: Negative result
• KW 23: Pfingstferien
• KW 24+25: Support: Positive result 1 I, Support: Positive result 1 II, Support: Positive result 1 III
• KW 26: Support: Positive result 2 I, Support: Positive result 2 II, Support: Comparison
• KW 27: Normal forms I, Normal forms II, Normal forms III, Normal forms IV
• KW 28: Weighted regular tree grammars: Definition
• KW 29: Wrtg: Simplifications I, Wrtg: Simplifications II, Wrtg - Wta

Material

An dieser Stelle werden wöchentlich Teile des Vorlesungsskripts erscheinen. Die dazugehörigen Referenzen finden Sie separat am Ende der folgenden Liste. Die Materialien sind nur aus dem Netz der TU abrufbar, nutzen Sie ggf VPN.

• Preliminaries
• Basic model
• Relationship semantics
• Support (aktualisiert am 19.06.)
• Normal forms
• Weighted regular tree grammars (aktualisiert am 16.07.)
• Bibliography

Ü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 16)
• 2. Übungsblatt (KW 17)
• 3. Übungsblatt (KW 18)
• 4. Übungsblatt (KW 19)
• 5. Übungsblatt (KW 20)
• 6. Übungsblatt (KW 21)
• 7. Übungsblatt (KW 22)
• 8. Übungsblatt (KW 24)
• 9. Übungsblatt (KW 25)
• 10. Übungsblatt (KW 26)
• 11. Übungsblatt (KW 27)
• 12. Übungsblatt (KW 28)
• 13. Übungsblatt (KW 29)

Termine

• Montags, 2. DS (09:20 – 10:50 Uhr), APB/E006: Vorlesung
• Donnerstags, 4. DS (13:00 – 14:30 Uhr), APB/E010: Vorlesung
• Mittwochs, 2. DS (09:20 – 10:50 Uhr), APB/E010: Übung

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