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

Übungen

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. [doiurl]
  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. [doiurl]
  10. Goguen, J.A. and Thatcher, J.W. 1974. Initial algebra semantics. 15th Annual Symposium on Switching and Automata Theory (SWAT 1974). [doiurl]
  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. [doiurl]
  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
    Fax: +49 (0) 351 463-37959
  • Thomas Ruprecht, M.Sc.
    Tel.: +49 (0) 351 463-38469
    Fax: +49 (0) 351 463-37959
Stand: 16.07.2018 14:45 Uhr