Formale Baumsprachen im Sommersemester 2018

Inhalt

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 einer Sprache in eine andere zu finden.

In dieser Vorlesung 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.

Vorlesungen

• 2018-04-12: Einführung, Bäume und Eigenschaften von Bäumen [Baader and Nipkow 1998] [Gécseg and Steinby 1984] [Gécseg and Steinby 1997] [Engelfriet 2015]
• 2018-04-19: Eigenschaften und Manipulation von Bäumen, und Universelle Algebra [Grätzer 1968] [Grätzer 1979]
• 2018-04-26: Endliche Baumautomaten, bottom-up und top-down Determinismus
• 2018-05-03: Top-down determistische FTA und reguläre Baumgrammatiken
• 2018-05-10: keine Vorlesung (Christi Himmelfahrt)
• 2018-05-17: Äquivalenz von endlichen Baumautomaten und regulären Baumgrammatiken
• 2018-05-24: keine Vorlesung (Pfingsten)
• 2018-05-31: yield(Rec) = CF [Thatcher 1967]
• 2018-06-07: Abschlusseigenschaften von Rec
• 2018-06-14: keine Vorlesung (Output)
• 2018-06-21: Abschlusseigenschaften von Rec [Bar-Hillel et al. 1961]
• 2018-06-28: Satz von Kleene, Myhill-Nerode-Theorem [Thatcher and Wright 1968] [Kozen 1992]
• 2018-07-05: Myhill-Nerode-Theorem
• 2018-07-12: Büchi-Theorem [Thatcher and Wright 1968]

Übungen

• 2018-04-18: Definitionen und Beweise durch strukturelle Induktion
• 2018-04-25: Beweise durch strukturelle Induktion, Universelle Algebra
• 2018-05-02: Universelle Algebra, Bottom-up deterministische FTA
• 2018-05-09: FTA und reguläre Baumgrammatiken
• 2018-05-16: keine Übung
• 2018-05-23: keine Übung (Pfingsten)
• 2018-05-30: Äquivalenz von Baumautomaten und -grammatiken, Beweise durch strukturelle Induktion
• 2018-06-06: keine Übung (Dies academicus)
• 2018-06-13: yield(Rec) = CF, Abschlusseigenschaften
• 2018-06-20: Abschlusseigenschaften II
• 2018-06-27: Abschlusseigenschaften III
• 2018-07-04: Satz von Kleene
• 2018-07-11: Myhill-Nerode-Theorem
• 2018-07-18: Büchi-Theorem

Termine

• Vorlesung: Donnerstag, 4. DS (13:00–14:30 Uhr), APB/E010
• Übung: Mittwoch, 2. DS (9:20–10:50 Uhr), APB/E010

Die erste Vorlesung findet am 12.04. und die erste Übung am 18.04. statt.

Referenzen

1. Baader, F. and Nipkow, T. 1998. Term Rewriting and All That. Cambridge University Press.
2. Bar-Hillel, Y., Perles, M.A., and Shamir, E. 1961. On Formal Properties of Simple Phrase Structure Grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung 14, 1–4, 143–172. [doi]
3. Berstel, J. and Reutenauer, C. 1988. Rational series and their languages. .
4. Büchse, M., May, J., and Vogler, H. 2010. Determinization of weighted tree automata using factorizations. Journal of Automata, Languages and Combinatorics 15, 3/4, 229–254. [url]
5. Droste, M. and Gastin, P. 2005. Weighted automata and weighted logics. In: L. Caires, G.F. Italiano, L. Monteiro, C. Palamidessi and M. Yung, eds., Automata, Languages and Programming. Springer, 513–525. [doi]
6. Droste, M. and Vogler, H. 2006. Weighted tree automata and weighted logics. Theoretical Computer Science 366, 3, 228–247. [doi, url]
7. Engelfriet, J. 2015. Tree Automata and Tree Grammars. Computing Research Repository (CoRR). [arXiv]
8. Engelfriet, J. 1975. Tree Automata and Tree Grammars. Aarhus University.
9. Fülöp, Z., Stüber, T., and Vogler, H. 2012. A Büchi-Like Theorem for Weighted Tree Automata over Multioperator Monoids. Theory of Computing Systems 50, 2, 241–278. [doi, url]
10. Goguen, J.A. and Thatcher, J.W. 1974. Initial algebra semantics. 15th Annual Symposium on Switching and Automata Theory (SWAT 1974). [doi, url]
11. 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, url]
12. Grätzer, G. 1968. Universal Algebra. Van Nostrand, Princeton (NJ). [doi]
13. Grätzer, G. 1979. General Lattice Theory. Birkhäuser Verlag.
14. Gécseg, F. and Steinby, M. 1984. Tree Automata. Akadémiai Kiadó. [url]
15. 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]
16. Kirsten, D. 2009. The Support of a Recognizable Series over a Zero-Sum Free, Commutative Semiring Is Recognizable. Proceedings of the 13th International Conference on Developments in Language Theory (DLT 2009), Springer Berlin Heidelberg, 326–333. [doi]
17. Kozen, D. 1992. On the Myhill-Nerode Theorem for Trees. Bulletin of the European Association of Theoretical Computer Science 47, 170–173. [url]
18. 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]
19. Thatcher, J.W. and Wright, J.B. 1968. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory 2, 1, 57–81. [doi]

Kontakt

• Prof. Dr.-Ing. habil. Dr. h.c./Univ. Szeged
  Heiko Vogler
  Tel.: +49 (0) 351 463-38232
• Thomas Ruprecht, M.Sc.
  Tel.: +49 (0) 351 463-38469