TUD Logo

TUD Startseite » ... » Lehre » Sommersemester 2017 » Formale Baumsprachen

Grundlagen der Programmierung

Formale Baumsprachen im Sommersemester 2017

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.

Termine

  • Donnerstags, 4. DS (13:00–14:30 Uhr), APB/E010: Vorlesung
  • Mittwochs, 2. DS (09:20–10:50 Uhr), APB/E010: Ãœbung
Die erste Vorlesung findet am 6. April statt.
Die erste Ãœbung wird verlegt auf Dienstag, 11. April, 13:00–14:30 (4. DS), Raum APB/3027. Die verbleibenden Ãœbungstermine finden planmäßig am Mittwoch, 2. DS, statt.
Die Ãœbung am 17. Mai (Dies Academicus) fällt aus.
In der Woche vom 05.06. bis 11.06. (Pfingsten) finden keine Lehrveranstaltungen statt.
Am 15.06. (Output) findet keine Vorlesung statt.

Vorlesungen

  • 2017-04-06: motivation, trees and tree languages, some characteristics of trees, manipulation of trees. Literature: [GS84], [Eng75]
  • 2017-04-13: basics of universal algebra, bu-det fta, fta. Literature: [Grä68], [Eng75], [GS84], [GS97]
  • 2017-04-20: Rec(Σ) = bud-Rec(Σ), top-down determinism, run semantics
  • 2017-04-27: regular tree grammars, Rec(Σ) = Reg(Σ)
  • 2017-05-04: yield(Rec) = CF
  • 2017-05-11: closure properties of Rec (I)
  • 2017-05-18: closure properties of Rec (II)
  • 2017-06-01: Rec = Rat
  • 2017-06-08: keine Vorlesung (Pfingsten)
  • 2017-06-15: keine Vorlesung (Output)
  • 2017-06-22: Myhill-Nerode theorem for trees
  • 2017-06-29: monadic second-order logic on trees

Übungen

  • 2017-04-11: proof by structural induction; Ãœbungsblatt 1 (definition by structural induction, proof by structural induction)
  • 2017-04-19: Ãœbungsblatt 2 (universal algebra, bu-det fta)
  • 2017-04-26: Ãœbungsblatt 3 (bu-det fta, string automata I, string automata II)
  • 2017-05-03: Ãœbungsblatt 4 (regular tree grammars, relatedness, tree manipulation)
  • 2017-05-10: Ãœbungsblatt 5 (yield(Rec) and CF, unranked tree automata and Haskell), ausgewählte Lösungen: UTA.hs
  • 2017-05-17: keine Ãœbung (Dies Academicus)
  • 2017-05-24: Ãœbungsblatt 6 (complement of a string automaton; closure of Rec under intersection, union, and complement; concatenation and Kleene star for recognizable tree languages)
  • 2017-05-31: Ãœbungsblatt 7 (relabelings; construction of Bar-Hillel, Perles, and Shamir; construction for Rec ⊆ Rat)
  • 2017-06-07: keine Ãœbung (Pfingsten)
  • 2017-06-14: Ãœbungsblatt 8 (local tree languages, path languages)
  • 2017-06-21: Ãœbungsblatt 9 (path languages, context-free grammars with latent annotations)
  • 2017-06-28: Ãœbungsblatt 10 (Myhill-Nerode theorem for trees (I) and (II))
  • 2017-07-05: Ãœbungsblatt 11 (monadic second-order logic on trees)
  • 2017-07-12: Ãœbungsblatt 12 (Rec = MSO-definable, consultation)

Literatur

[BPS61] Y. Bar-Hillel, M. Perles and E. Shamir. On formal properties of simple phrase structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 1961.
[Tha67] James W. Thatcher. Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. Journal of Computer and System Sciences, 1967. doi:10.1016/S0022-0000(67)80022-9.
[Grä68] George Grätzer. Universal algebra. D. van Nostrand, 1968. doi:10.1007/978-0-387-77487-9.
[TW68] James W. Thatcher and Jesse B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory, 1968. doi:10.1007/BF01691346.
[TW74] James W. Thatcher and Jesse B. Wright. Initial algebra semantics. 15th Annual Symposium on Switching and Automata Theory, 1974. doi:10.1109/swat.1974.13.
[Eng75] Joost Engelfriet. Tree automata and tree grammars. Technical Report DAIMI FN-10, Aarhus University, 1975. See also 2015, arXiv:1510.02036 [cs.FL].
[Gog+77] J. A. Goguen, and James W. Thatcher, E. G. Wagner, and Jesse B. Wright. Initial Algebra Semantics and Continuous Algebras. Journal of the Association for Computational Machinery, 1977. doi:10.1145/321992.321997.
[GS84] Ferenc Gécseg and Magnus Steinby. Tree Automata. Akadémiai Kiadó, 1984. See also 2015, arXiv:1509.06233 [cs.FL].
[Koz92] Dexter Kozen. On the Myhill-Nerode Theorem for Trees. Bulletin of the European Association of Theoretical Computer Science 47, 1992. url:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51.5546&rep=rep1&type=pdf.
[GS97] Ferenc Gécseg and Magnus Steinby. Tree languages. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, pages 1–68. Springer Berlin Heidelberg, 1997. doi:10.1007/978-3-642-59126-6_1.
[BN98] Franz Baader and Tobias Nipkow. Term Rewriting and All That. Cambridge University Press, 1998.
Stand: 10.7.2017, 8:27 Uhr
Autor: Dipl.-Inf. Tobias Denkinger

Kontakt
Prof. Dr.-Ing. habil. Dr. h.c./Univ. Szeged
Heiko Vogler

Tel.: +49 (0) 351 463-38232
Fax: +49 (0) 351 463-37959
E-Mail-Kontaktformular

Dipl.-Inf.
Tobias Denkinger

Tel.: +49 (0) 351 463-38487
Fax: +49 (0) 351 463-37959
E-Mail-Kontaktformular