Gewichtete Baumautomaten im Wintersemester 2019/20

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 sowie verschiedene ihrer formalen Eigenschaften kennenlernen und beweisen, 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.

• 2019-10-15: 1. Übungsblatt
• 2019-10-22: 2. Übungsblatt
• 2019-10-29: 3. Übungsblatt
• 2019-11-05: 4. Übungsblatt
• 2019-11-12 und 2019-11-19: 5. Übungsblatt
• 2019-11-26 und 2019-12-03: 6. Übungsblatt
• 2019-12-10 und 2019-12-17: 7. Übungsblatt
• 2020-01-07: 8. Übungsblatt
• 2020-01-14: 9. Übungsblatt
• 2020-01-21: 10. Übungsblatt
• 2020-01-28: 11. Übungsblatt

Literatur

1. Baader, F. and Nipkow, T. 1998. Term Rewriting and All That. Cambridge University Press.
2. Droste, M., Stüber, T., and Vogler, H. 2010. Weighted finite automata over strong bimonoids. Information Sciences 180, 1, 156–166. [doi]
3. Droste, M. and Vogler, H. 2012. Weighted automata and multi-valued logics over arbitrary bounded lattices. Theoretical Computer Science 418, 14–36. [doi]
4. Eilenberg, S. 1974. Automata, Languages, and Machines. Academic Press, Inc., Orlando, FL, USA.
5. Engelfriet, J. 2015. Tree Automata and Tree Grammars. (lecture notes). [url]
6. 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. [doi, url]
7. Goguen, J.A., Thatcher, J.W., Wagner, E.G., and Wright, J.B. 1977. Initial Algebra Semantics and Continuous Algebras. Journal of the Association for Computational Machinery 24, 1, 68–95. [doi]
8. Golan, J.S. 1999. Semirings and their Applications. Springer Netherlands. [doi]
9. Grätzer, G. 1968. Universal Algebra. Van Nostrand, Princeton (NJ). [doi]
10. Gécseg, F. and Steinby, M. 1984. Tree Automata. Akadémiai Kiadó. [url]
11. Hebisch, U. and Weinert, H.J. 1998. Semirings – Algebraic Theory and Applications in Computer Science. World Scientific, Singapore. [doi]
12. Wechler, W. 1992. Universal Algebra. In: Universal Algebra for Computer Scientists. Springer Berlin Heidelberg, Berlin, Heidelberg, 135–241. [doi, url]
13. Ćirić, M., Droste, M., Ignjatović, J., and Vogler, H. 2010. Determinization of weighted finite automata over strong bimonoids. Information sciences 180, 18, 3497–3520.
14. Ésik, Z. and Kuich, W. 2003. Formal Tree Series. Journal of Automata, Languages and Combinatorics 8, 2, 219–285.

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