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
- 1. Übung, 22.04.2015: Übungsblatt
- 2. Übung, 29.04.2015: Übungsblatt
- 3. Übung, 07.05.2015: Übungsblatt
- 4. Übung, 13.05.2015: Übungsblatt
- 5. Übung, 20.05.2015: Übungsblatt
- 6. Übung, 03.06.2015: Übungsblatt
- 7. Übung, 10.06.2015: Übungsblatt
- 8. Übung, 17.06.2015: Übungsblatt
- 9. Übung, 26.06.2015: Übungsblatt
- 10. Übung, 01.07.2015: Übungsblatt
- 11. Übung, 08.07.2015: Übungsblatt
- 12. Übung, 15. und 16.07.2015: Übungsblatt
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. |