Hauptregion der Seite anspringen
TU Dresden — Fakultät Informatik — Institut für Theoretische Informatik

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: 30.08.2017 12:29 Uhr