Hauptregion der Seite anspringen
TU Dresden — Fakultät Informatik — Institut für Theoretische Informatik

Theorie der Gewichteten Baumautomaten im Wintersemester 2021/22

Aktuelle Hinweise:

  • Die Vorlesung am 09.12.2021 entfällt!
  • Vorlesung und Übung finden online statt. Die Links werden im OPAL-Kurs bekanntgegeben.
  • Für weitere Informationen zu corona-bedingten Regelungen bitte die Corona-FAQ der TU Dresden konsultieren.

Einführung

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 sowie verschiedene ihrer formalen Eigenschaften kennenlernen und beweisen, z.B. Resultate zur Charakterisierung und Determinisierung.

Termine

Vorlesung:

  • Montag, 3. DS (11:10 Uhr bis 12:40 Uhr), online
  • Donnerstag, 3. DS (11:10 Uhr bis 12:40 Uhr), online

Übung: Dienstag, 4. DS (13:00 Uhr bis 14:30 Uhr), online

Der Übungsbetrieb startet in der 42. KW (d.h. am 19.10.).

Materialien

Hinweis: Sie können sich anhand des vorherigen Durchlaufs einen Überblick verschaffen. Dort kann weiterhin auf die Audioaufzeichnungen zugegriffen werden. Achtung: für die Prüfung des aktuellen Durchlaufs sind diese Aufzeichnungen nicht relevant!

Der Download der Vorlesungsmaterialien ist auf das Netzwerk der TU Dresden beschränkt. Für Downloads aus anderen Netzen können Sie den VPN-Zugang des ZIHs benutzen.

Vorlesung

An dieser Stelle werden wöchentlich Teile des Vorlesungsskripts erscheinen. Die dazugehörigen Referenzen finden Sie separat am Ende dieser Seite. Das Skript ist urheberrechtlich geschützt und darf nur für das persönliche Studium verwendet werden. Die Verbreitung ist untersagt.

Übung

An dieser Stelle werden im Verlauf des Semesters die Übungsblätter bereitgestellt. Aufgaben, die in der aufgeführten Woche nicht bearbeitet wurden, werden in der darauffolgenden Woche nachgeholt.

Literatur

  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
  • Dipl.-Inf. Richard Mörbitz
    Tel.: +49 (0) 351 463-38487
Stand: 28.01.2022 16:01 Uhr