Inhalt

In vielen Bereichen der Informatik werden Bäume verwendet, um Daten zu strukturieren und hierarchische Abhängigkeiten zwischen einzelnen Daten darzustellen; z.B. kann die Struktur eines Satzes einer natürlichen Sprache als Baum (parse tree) dargestellt werden. Deshalb ist es von allgemeinem Interesse, Algorithmen bereitzustellen, welche Bäume auf bestimmte Eigenschaften untersuchen, Bäume durch Zuordnung von Gewichten bewerten, oder Bäume in andere Bäume überführen. In dieser Vorlesung werden wir die Theorie der gewichteten Baumautomaten behandeln.

Baumautomaten sind formale Modelle für Algorithmen zur Beschreibung von Mengen von Bäumen. In dieser Vorlesung werden wir ihre grundlegenden Definitionen auf theoretischem Niveau einführen, und verschiedene ihrer formalen Eigenschaften kennenlernen und beweisen, so z.B. Resultate zur Charakterisierung und Determinisierung.

Termine

Die Lehrveranstaltung findet im Umfang V2/Ü2 statt.

  • Montags, 3. DS (11:10 – 12:40 Uhr), APB/E010: Vorlesung
  • Dienstags, 4. DS (13:00 – 14:30 Uhr), APB/E009: Übung

Übungsaufgaben

Nur aus dem Netz der TU abrufbar; ggf. über VPN herunterladen.

Literatur

  1. Engelfriet, J. 2015. Tree Automata and Tree Grammars. (lecture notes). [url]
  2. Fülöp, Z. and Vogler, H. 2009. Weighted Tree Automata and Tree Transducers. In: M. Droste, W. Kuich and H. Vogler, eds., Handbook of Weighted Automata. Springer Berlin Heidelberg, Berlin, Heidelberg, 313–403. [doiurl]
  3. Gécseg, F. and Steinby, M. 1984. Tree Automata. Akadémiai Kiadó. [url]

Kontakt

  • Prof. Dr.-Ing. habil. Dr. h.c./Univ. Szeged
    Heiko Vogler
    Tel.: +49 (0) 351 463-38232
    Fax: +49 (0) 351 463-37959
  • Dipl.-Inf. Richard Mörbitz
    Tel.: +49 (0) 351 463-38487
    Fax: +49 (0) 351 463-37959
Stand: 18.10.2019 09:46 Uhr