Formale Baumsprachen im Sommersemester 2019

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.

Allgemeine Hinweise

• Fragen bitte an Thomas Ruprecht.

Termine

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

Die erste Vorlesung findet am 4. April statt und die erste Übung am 10. April.

Vorlesungen

• 2019-04-04: binary relations, ranked alphabets, trees [Baader and Nipkow 1998; Gécseg and Steinby 1984; Gécseg and Steinby 1997; Engelfriet 1975]
• 2019-04-11: tree characteristics and manipulations, proof by structural induction, Σ-algebras, homomorphisms, congruence relations, subalgebras, freely generated algebras, initial algebras [Grätzer 1968; Grätzer 1979]
• 2019-04-18: Σ-term algebras, bu-det ftas, (nondeterministic) ftas, powerset construction [Engelfriet 1975; Gécseg and Steinby 1984; Gécseg and Steinby 1997; Fülöp and Vogler 1998]
• 2019-04-25: powerset construction, td-det ftas
• 2019-05-02: tdd-Rec(Σ) ⊊ bud-Rec(Σ), run semantics, L = Lᵣ
• 2019-05-09: regular tree grammars (RTGs), normal form RTGs, final-state normal form [Brainerd 1969]
• 2019-05-16: relatedness, Rec(Σ) = Reg(Σ), CFGs, yield
• 2019-05-23: normal form CFGs, e-relatedness, yield(Rec) = CF [Thatcher 1967]
• 2019-05-30: keine Vorlesung (Christi Himmelfahrt)
• 2019-06-06: closure of REC under intersection, union, and complement
• 2019-06-13: keine Vorlesung (Pfingstwoche)
• 2019-06-20: keine Vorlesung (Output)
• 2019-06-27: closure of REC under concatenation, Kleene star, and relabelling; string automata
• 2019-07-04: keine Vorlesung
• 2019-07-11: 11. Vorlesung

Übungen

• 2019-04-10: 1. Übungblatt: finite state (string) automata; ranked alphabets; tree domain
• 2019-04-17: 2. Übungblatt: definition by structural induction; proof by structural induction
• 2019-04-24: 3. Übungblatt: universal algebra; bu-det fta
• 2019-05-01: keine Übung (Feiertag)
• 2019-05-08: 4. Übungblatt: string automata; non-deterministic bottom-up tree automata; non-deterministic top-down tree automata
• 2019-05-15: 5. Übungblatt: regular tree grammars; unranked tree automata in Haskell
• 2019-05-22: keine Übung (Dies academicus)
• 2019-05-29: 6. Übungblatt: relatedness; yield(REC) and CF
• 2019-06-05: 7. Übungblatt: complement of a string automaton
• 2019-06-12: keine Übung (Pfingstwoche)
• 2019-06-19: keine Übung (Jubiläumsfeier)
• 2019-06-26: 8. Übungblatt: closure of REC under intersection, union, and complement; string automata II
• 2019-07-03: 9. Übungblatt: concatenation and Kleene star for recognizable tree languages
• 2019-07-10: 10. Übungblatt: relabellings

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
• Thomas Ruprecht, M.Sc.
  Tel.: +49 (0) 351 463-38469