Hauptregion der Seite anspringen

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

Übungen

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

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
    Fax: +49 (0) 351 463-37959
  • Dr. rer. nat. Luisa Herrmann
    Tel.: +49 (0) 351 463-38487
    Fax: +49 (0) 351 463-37959
Stand: 07.05.2021 15:50 Uhr