Formale Baumsprachen im Sommersemester 2016

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, 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
Donnerstags, 4. DS (13:00–14:30 Uhr), APB/E010: Vorlesung
Mittwochs, 2. DS (9:20–10:50 Uhr), APB/E010: Übung

Die erste Vorlesung findet am 4. April 2016 statt, die erste Übung am 13. April 2016.
Die Übung vom 01. Juni 2016 wird verlegt auf Freitag, 03. Juni 2016, 1. DS (07:30–09:00 Uhr), APB/3027.
Die Vorlesung am 09. Juni 2016 wird in den Raum APB/3027 verlegt.
Die letzte Vorlesung findet am 11. Juli 2016 und die letzte Übung am 13. Juli 2016 statt.

Übungsaufgaben

2016-04-13: Übungsblatt 1 (definition and proof by structural induction, universal algebra)
2016-04-20: Übungsblatt 2 (bu-det fta, finite state automata, regular tree grammars)
2016-05-04: Übungsblatt 3 (closure results for Rec, finite state automata and matrices)
2016-05-11: Übungsblatt 4 (relabelings, inverse yield, recognizable and rational languages)
2016-05-25: Übungsblatt 5 (Myhill-Nerode theorem for trees, MSO-logic on trees)
2016-06-03: Übungsblatt 6 (recognizable and MSO-definable, pumping lemma for recognizable tree languages)
2016-06-08: Übungsblatt 7 (some weight algebras; yield, pos, height and wta)
2016-06-15: Übungsblatt 8 (scalar multiplication, analysis of wta, zigzag I)
2016-06-22: Übungsblatt 9 (zigzag II, representation and implementation lemma)
2016-06-29: Übungsblatt 10 (semantics of weighted MSO, unrestricted MSO and recognizability)
2016-07-06: Übungsblatt 11 (closure of recognizable step functions, weighted automata and logics over M-monoids)
2016-07-13: Übungsblatt 12 (for every M-expression there is an equivalent M-wta)

Behandelte Themen

2016-04-04: motivation, binary relations
2016-04-07: trees, tree languages, tree characteristics, some tree transformations, definition and proof by structural induction
2016-04-11: example for proof by structural induction, Σ-algebras, homomorphisms, congruence relations, subalgebras, freely generated and initial algebras, term algebras, syntax and semantics of bu-det fta, bu-det recognizability
2016-04-14: non-deterministic fta, power set construction, td-det fta
2016-04-18: bu-rec. languages that are not td-rec., run semantics of fta, regular tree grammars
2016-04-21: normal form rtgs and rtgs in final state normal form, equivalence of fta and rtg
2016-04-25: the yields of recognizable tree languages are exactly the context-free string languages
2016-04-28: recognizable tree languages are closed under union, intersection, difference, complement, and Kleene-star
2016-05-02: recognizable tree languages are closed under relabeling, inverse yield is recognizable
2016-05-09: the recognizable tree languages are exactly the rational tree languages
2016-05-12: Myhill-Nerode theorem for trees, syntax of MSO-formulas on trees
2016-05-23: semantics of MSO-formulas on trees, recognizable implies definable (part I)
2016-05-26: recognizable implies definable (part II), definable implies recognizable (part I)
2016-05-30: definable implies recognizable (part I), decidability results
2016-06-02: weight algebras, weighted tree languages, weighted tree automata, initial algebra semantics
2016-06-06: run semantics; equivalence of run and initial algebra semantics for distributive strong bimonoids
2016-06-09: support of recognizable tree languages
2016-06-13: normal forms
2016-06-16: determinization for locally finite semirings
2016-06-20: inverse image theorem, syntax and semantics of weighted MSO for trees and commutative semirings [DV06, Defs. 4.1 and 4.2]
2016-06-23: recognizable implies definable, definable implies recognizable (part I)
2016-06-27: definable implies recognizable (part II)
2016-06-30: M-monoids, wta over M-monoids
2016-07-04: M-expressions, recognizable implies definable, further reading: slides by Paul Gastin
2016-07-07: definable implies recognizable, syntactical transformation from srMSO to M-expressions (part I)
2016-07-11: syntactical transformation from srMSO to M-expressions (part II) and from M-expressions to srMSO

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
[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
[Grä79]	George Grätzer. General Lattice Theory. Birkhäuser Verlag, 1979. isbn:9780122957505.
[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.
[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.
[Kir09]	Daniel Kirsten. The Support of a Recognizable Series over a Zero-Sum Free, Commutative Semiring Is Recognizable. Proceedings of the 13th International Conference on Developments in Language Theory, 2009. doi:10.1007/978-3-642-02737-6_26.
[BMV10]	Matthias Büchse, Jonathan May, and Heiko Vogler. Determinization of weighted tree automata using factorizations. Journal of Automata, Languages and Combinatorics, 2010. url:https://www.inf.tu-dresden.de/content/institutes/thi/gdp/pubs/2009/determ2.pdf
[FSV12]	Zoltán Fülöp, Torsten Stüber, and Heiko Vogler. A Büchi-Like Theorem for Weighted Tree Automata over Multioperator Monoids. Theory of Computing Systems 50(2), pp. 241-278, 2012. doi:10.1007/s00224-010-9296-1.

Stand: 30.08.2017 12:29 Uhr