Theorie der formalen Baumsprachen im Sommersemester 2022

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ürlicher 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.

Einschreibung

Für die Teilnahme an der Lehrveranstaltung ist es notwendig, sich im OPAL-Kurs Theorie der formalen Baumsprachen SS 2022 einzutragen.

Termine

• Montag, 2. DS (9:20 Uhr – 10:50 Uhr), APB/E006/U: Vorlesung
• Donnerstag, 2. DS (9:20 Uhr – 10:50 Uhr), APB/E010/U: Vorlesung
• Donnerstag, 3. DS (10:50 Uhr – 11:10 Uhr), APB/E010/U: Übung

Vorlesungen

An dieser Stelle werden im Laufe des Semesters Informationen und begleitende Materialien zu den Vorlesungen veröffentlicht.

Übungen

Die Materialien sind nur aus dem Netz der TU abrufbar, nutzen Sie ggf. VPN.

• 1. Übungsblatt
• 2. Übungsblatt
• 3. Übungsblatt
• 4. Übungsblatt
• 5. Übungsblatt
• 6. Übungsblatt
• 7. Übungsblatt
• 8. Übungsblatt
• 9. Übungsblatt
• 10. Übungsblatt
• 11. Übungsblatt
• 12. Übungsblatt

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