Theorie der formalen Baumsprachen im Sommersemester 2021

Hinweis: Diese Vorlesung überschneidet sich inhaltlich nicht mit den vorangegangenen Vorlesungen Theorie der gewichteten Baumautomaten WS20/21 und Formale Baumsprachen SS20 (in welchen gewichtete Baumsprachen betrachtet wurden).

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.

Aktuelle Hinweise

Aufgrund von SARS-CoV-2 und den damit verbundenen Maßnahmen, verfahren wir wie folgt:

• Die Vorlesungen beginnen mit dem regulären Semesterstart zum 12.04. zunächst virtuell.
• Bitte schreiben Sie sich in den zugehörigen OPAL-Kurs ein.
• Prof. Vogler wird zu den Vorlesungsterminen virtuelle Vorlesungen via BBB abhalten. Der Link zu diesen Vorlesungen wird auf OPAL veröffentlicht.
• Die Übungen finden ebenfalls virtuell via BBB statt.
• Weitere Maßnahmen und Anpassungen bzw. ein Übergang zum regulären Präsenzbetrieb erfolgen entsprechend den Empfehlungen der Universitätsleitung.

Einschreibung

Für die Teilnahme an der Lehrveranstaltung ist es notwendig, sich im OPAL-Kurs Theorie der formalen Baumsprachen SS 2021 einzutragen. Über diesen Kurs werden die BBB-Links zu den Vorlesungen und Übungen verteilt.

Termine

• Montags, 2. DS (09:20 – 10:50 Uhr): Vorlesung
• Donnerstags, 3. DS (11:10 – 12:40 Uhr): Vorlesung
• Mittwochs, 2. DS (09:20 – 10:50 Uhr): Übung

Vorlesungen

• 2021-04-12: binary relations
• 2021-04-15: ranked alphabets, trees [Baader and Nipkow 1998; Gécseg and Steinby 1984; Gécseg and Steinby 1997; Engelfriet 1975; Fülöp and Vogler 1998]
• 2021-04-19: tree characteristics and manipulations, proof by structural induction
• 2021-04-22: Σ-algebras, homomorphisms, subalgebras [Grätzer 1968; Grätzer 1979]
• 2021-04-26: Σ-term algebras, bu-det ftas
• 2021-04-29: bu-det ftas, (nondeterministic) ftas [Engelfriet 1975; Gécseg and Steinby 1984; Gécseg and Steinby 1997; Fülöp and Vogler 1998]
• 2021-05-03: bud-Rec(Σ) ⊆ Rec(Σ), powerset construction
• 2021-05-06: td-det ftas, tdd-Rec(Σ) ⊊ bud-Rec(Σ)
• 2021-05-10: run semantics
• 2021-05-17: regular tree grammars (RTGs)
• 2021-05-20: normal form RTGs, final-state normal form
• 2021-05-31: relatedness, Rec(Σ) = Reg(Σ), yield
• 2021-06-03: Video, normal form CFGs, e-relatedness, yield(Rec) = CF [Thatcher 1967]
• 2021-06-07: closure of REC under tree concatenation and Kleene star
• 2021-06-10: Video, closure of REC under relabeling, string automata
• 2021-06-14: closure of REC under intersection, union, and complement, Rec(Σ) = Rat(Σ)
• 2021-06-17: Rec(Σ) = Rat(Σ)
• 2021-06-21: Myhill-Nerode
• 2021-06-24: Myhill-Nerode
• 2021-06-28: Video, Myhill-Nerode
• 2021-07-01: Video, Einführung Logikcharacterisierung

Übungen

Übungsaufgaben werden wöchentlich an dieser Stelle veröffentlich. Die Materialien sind nur aus dem Netz der TU abrufbar, nutzen Sie ggf VPN.

• 1. Übungsblatt (2021-04-21),
• 2. Übungsblatt (2021-04-28),
• 3. Übungsblatt (2021-05-05),
• 4. Übungsblatt (2021-05-12),
• 5. Übungsblatt (2021-05-19),
• 6. Übungsblatt (2021-06-02),
• 7. Übungsblatt (2021-06-09),
• 8. Übungsblatt (2021-06-16),
• 9. Übungsblatt (2021-06-23),
• 10. Übungsblatt (2021-06-30),
• 11. Übungsblatt (2021-07-14),
• 12. Übungsblatt (2021-07-21)

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