Hauptregion der Seite anspringen

Formale Baumsprachen im Sommersemester 2015

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. Bei der Verarbeitung natürlichen Sprache (natural language processing; nlp) ist es beispielsweise wichtig, die Wahrscheinlichkeit, ob ein Satz unter Beachtung grammatikalischer Regeln wohl-strukturiert ist, oder mögliche Übersetzungen eines Satzes einer Sprache in eine andere zu bestimmen.

Gewichtete Baumautomaten (weighted tree automata) sind für solche Algorithmen gut geeignet. 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

  • Montags, 2. DS (9:20–10:50 Uhr), APB/E009: Vorlesung
  • Mittwochs, 2. DS (9:20–10:50 Uhr), APB/E010: Übung
  • Donnerstags, 4. DS (13:00–14:50 Uhr), APB/E010: Vorlesung

Die erste Vorlesung findet am 13. April 2015 statt.
Die erste Übung findet am 22. April 2015 statt.
Die Übung vom 6. Mai wird verlegt auf 7. Mai, 5. DS, APB/E006.
In der Woche vom 25. bis 31. Mai finden weder die Vorlesungen noch die Übung statt.
Die Übung vom 24. Juni wird verlegt auf 26. Juni, 2. DS, APB/3027.
Die Vorlesung am Donnerstag, dem 2. Juli, fällt wegen Output aus.
Die Vorlesung am Donnerstag, dem 16. Juli, wird durch eine Übung ersetzt.
Ab einschließlich der Woche vom 20.07.2015 finden keine Vorlesungen und Übungen mehr statt.

Übungsaufgaben

Behandelte Themen

1. Vorlesung, 13.04.2015

Themen: binäre Relationen, Bäume, Baumsprachen
Literatur: [BN98], [GS84], [GS97], [Eng75]

2. Vorlesung, 16.04.2015

Themen: Kontexte, Definition und Beweis durch strukturelle Induktion

3. Vorlesung, 20.04.2015

Themen: Algebra, Kongruenzrelation, Unteralgebra, Homomorphismus, frei erzeugte Algebra, Termalgebra
Literatur: [Grä68]

4. Vorlesung, 23.04.2015

Themen: endliche Baumautomaten, bottom-up Determinismus, Rec(Σ) ⊆ bud-Rec(Σ) (Potenzmengenkonstruktion)
Literatur: [GS84], [GS97], [Eng75]

5. Vorlesung, 27.04.2015

Themen: top-down Determinismus, Lauf-Erkennbarkeit, tdd-Rec(Σ) “⊊” bud-Rec(Σ) = Rec(Σ), reguläre Baumgrammatiken

6. Vorlesung, 30.04.2015

Themen: Rec(Σ) = Reg(Σ)

7. Vorlesung, 04.05.2015

Themen: yield(Rec) = CF
Literatur: [Tha67]

8. Vorlesung, 07.05.2015

Themen: Abschluss von Rec unter Schnitt, Vereinigung, Komplement, Baumkonkatenation, Kleene-Stern; Relabelings

9. Vorlesung, 11.05.2015

Themen: Abschluss von Rec unter Relabelings; Satz von Bar-Hillel, Perles, und Shamir
Literatur: [BPS61]

10. Vorlesung, 18.05.2015

Themen: rationale Baumsprachen, Rec = Rat

11. Vorlesung, 21.05.2015

Themen: Myhill-Nerode Charakterisierung von Rec
Literatur: [Koz92]

12. Vorlesung, 01.06.2015

Themen: Syntax der monadische Logik zweiter Ordnung für Bäume, Variablenzuordnungen
Literatur: [TW68]

13. Vorlesung, 04.06.2015

Themen: Modelle einer MSO-Formel, Erkennbarkeit impliziert MSO-Definierbarkeit

14. Vorlesung, 08.06.2015

Themen: MSO-Definierbarkeit impliziert Erkennbarkeit

15. Vorlesung, 11.06.2015

Themen: ausgewählte Entscheidbarkeitsresultate für erkennbare Baumsprachen, Semiringe

16. Vorlesung, 15.06.2015

Themen: charakteristische Abbildung, Summe und Produkt gewichteter Baumsprachen, Definition gewichteter Baumautomaten, erkennbare gewichtete Baumsprachen
weiterführende Literatur: [TW74], [Gog+77]

17. Vorlesung, 18.06.2015

Themen: Laufsemantik gewichteter Baumautomaten, Laufsemantik und initiale Algebrasemantik von gewichteten Baumautomaten stimmen überein

18. Vorlesung, 22.06.2015

Themen: Support Boolean-gewichteter Baumautomaten, Support Semiring-gewichteter Baumautomaten

19. Vorlesung, 25.06.2015

Themen: Support Semiring-gewichteter Baumautomaten
Literatur: [BR88]

20. Vorlesung, 29.06.2015

Themen: nicht jede erkennbare gewichtete Baumsprache ist deterministisch erkennbar, für lokal endliche Semiringe S gilt: Rec(Σ,S) = bud-Rec(Σ,S)
Literatur: [BV03]

21. Vorlesung, 06.07.2015

Themen: Inverse image theorem, erkennbare Stufenfunktion, Monadische Logik zweiter Stufe [DV06; Definitionen 4.1 und 4.2]
Literatur: für den Baumfall [DV06], für den Zeichenkettenfall [DG05]

22. Vorlesung, 09.07.2015

Themen: bestimmte Fragmente von MSO(K,Σ), Disambiguierung von Formeln, erkennbare gewichtete Baumsprachen sind REMSO-definierbar [DV06; Theorem 5.11]

23. Vorlesung, 13.07.2015, letzte Vorlesung

Themen: universelle Quantifikation erster Stufe von erkennbaren Stufenfunktionen ist erkennbar [DV06; Lemma 5.5]

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.
[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.
[BR88] Jean Berstel and Christophe Reutenauer. Rational series and their languages. Springer-Verlag Berlin, 1988.
[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.
[BV03] Björn Borchardt and Heiko Vogler. Determinization of finite state weighted tree automata. Journal of Automata, Languages and Combinatorics, 2003. url:http://dl.acm.org/citation.cfm?id=963859
[DG05] Manfred Droste and Paul Gastin. Weighted automata and weighted logics. Automata, Languages and Programming, 2005. doi:10.1007/11523468_42.
[DV06] Manfred Droste and Heiko Vogler. Weighted tree automata and weighted logics. Theoretical Computer Science 366, 2006. doi:10.1016/j.tcs.2006.08.025.
Stand: 16.10.2017 13:08 Uhr