Diese Vorlesung beeinhaltet (und erweitert) den Stoff der Vorlesungen Gewichtete Baumautomaten WS19/20 und Formale Baumsprachen SoSe 2020. Aus diesem Grund kann nur eine dieser Vorlesungen geprüft werden.

Aktuelle Hinweise

Wird noch ergänzt.

Einführung

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

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

Referenzen

  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
    Fax: +49 (0) 351 463-37959
  • Luisa Herrmann, M.Sc.
    Tel.: +49 (0) 351 463-38487
    Fax: +49 (0) 351 463-37959
Stand: 21.07.2020 10:46 Uhr