Formale Übersetzungsmodelle im Wintersemester 2017/18

Inhalt

In vielen Bereichen der Informatik werden Bäume verwendet, um Daten zu strukturieren und hierarchische Abhängigkeiten zwischen einzelnen Daten darzustellen; z.B. kann die Struktur eines Satzes einer natürlichen Sprache als Baum (parse tree) dargestellt werden. Deshalb ist es von allgemeinem Interesse, Algorithmen bereitzustellen, welche Bäume auf bestimmte Eigenschaften untersuchen, Bäume durch Zuordnung von Gewichten bewerten, oder Bäume in andere Bäume überführen. Hier werden wir die Theorie der bottom-up tree transducer und top-down tree transducer besprechen.

Tree Transducer (Baumübersetzer) sind formale Modelle für Algorithmen zur Überführung von Bäumen in Bäume. In dieser Vorlesung werden wir ihre grundlegenden Definitionen auf theoretischem Niveau einführen, und verschiedene ihrer formalen Eigenschaften kennenlernen, so z.B. zur Dekomposition von Transducern und zu ihrem Abschluss unter Komposition.

Termine

• Vorlesung: Montag, 4. DS (13:00–14:30 Uhr), APB/E009
• Übung: Donnerstag, 5. DS (14:50–16:20 Uhr), APB/E009

Verlegungen

• Die Übung vom 16.11. wird verlegt auf Di., 14.11., 4. DS (13:00–14:30 Uhr), APB/3027.

Vorlesung

• 2017-10-09: basic notions; definition by structural induction; characteristics of trees
• 2017-10-16: tree transformations; bottom-up tree transducers (syntax, derivation relation, induced tree transformation, some examples)
• 2017-10-23: non-determinism followed by copying (B1), checking followed by deletion (B2), decomposition of derivations, syntactic subclasses of BOT
• 2017-10-30: powerset construction
• 2017-11-06: decomposition of BOT, closure of (l-)BOT under FTA
• 2017-11-13: closure of (l-)BOT under HOM, (l-)BOT = REL ∘ FTA ∘ (l-)HOM, REG = REC
• 2017-11-20: closure of REC under l-BOT, domain of a bottup-up tree transducer is recognizable, top-down tree transducers (syntax and induced tree transformation)
• 2017-11-27: decomposition of TOP, ln-TOP = ln-BOT (Teil 1)
• 2017-12-04: ln-TOP = ln-BOT (Teil 2), h-TOP = HOM and r-TOP = REL, l-TOP ⊊ l-BOT
• 2017-12-11: TOP and BOT are incomparable
• 2017-12-18: Bakers theorems for BOT and TOP
• 2017-01-08: closure of l-BOT under composition, top-down tree transducers with regular look-ahead, a Hasse-diagram of tree transformations

Übungsaufgaben

• 2017-10-12: Übungsblatt 1 (ranked alphabets and trees; definition by structural induction)
• 2017-10-19: Übungsblatt 2 (relabeling and checking; proof by structural induction; gsms and bu-tts), Lösung zu Aufgabe 5
• 2017-10-26: Übungsblatt 3 (non-determinism and determinism; shape-preserving tree transformations; finite non-determinism; syntactic subclasses of BOT)
• 2017-11-02: Übungsblatt 4 (non-determinism and determinism 2; powerset construction; bounded growth property)
• 2017-11-09: Übungsblatt 5 (decomposition of BOT; bimorphism characterization of BOT)
• 2017-11-14: Übungsblatt 6 (BOT ∘ HOM ⊆ BOT; regular tree grammars)
• 2017-11-23: Übungsblatt 7 (symbolic derivation and Tiburon), Transducer in Tiburon: sol17a.tdtt, sol17b.tree, sol17z.ttst
• 2017-11-30: Übungsblatt 8 (decomposition of TOP, gsms and td-tts)
• 2017-12-07: Übungsblatt 9 (ln-BOT = ln-TOP, h-TOP = HOM and r-TOP = REL)
• 2017-12-14: Übungsblatt 10 (l-TOP ⊊ l-BOT, tree transducers and finite state automtata)
• 2018-01-04: Übungsblatt 11 (BOT² and TOP², exploring the search space)
• 2018-01-11: Übungsblatt 12 (Bakers theorem for BOT, Bakers theorem for TOP), Äquivalenzkette zu Aufgabe 27(b)
• 2018-01-18: Übungsblatt 13 (TOPᵣ ⊆ d-QREL ∘ TOP; l-BOT = l-TOPᵣ)

Referenzen

1. Baader, F. and Nipkow, T. 1998. Term rewriting and all that. Cambridge University Press, New York, NY, USA.
2. Baker, B.S. 1979. Composition of top-down and bottom-up tree transductions. Information and Control 41, 2, 186–213. [doi, url]
3. Bar-Hillel, Y., Perles, M., and Shamir, E. 1961. On Formal Properties of Simple Phrase Structure Grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung 14, 143–172.
4. Dershowitz, N. 1987. Termination of rewriting. Journal of Symbolic Computation 3, 1–2, 69–115. [doi]
5. Dershowitz, N. and Jouannaud, J.-P. 1990. Rewrite systems. In: J. van Leeuwen, ed., Handbook of Theoretical Computer Science (Vol. B). MIT Press, Cambridge, MA, USA, 243–320. [url]
6. Engelfriet, J. 1975. Bottom-up and top-down tree transformations – a comparison. Mathmatical systems theory 9, 2, 198–231. [doi]
7. Engelfriet, J. 1976. Top-down tree transducers with regular look-ahead. Mathmatical systems theory 10, 1, 289–303. [doi]
8. Engelfriet, J. 1982. Three hierarchies of transducers. Mathmatical systems theory 15, 1, 95–125. [doi]
9. Engelfriet, J. 2015. Tree Automata and Tree Grammars. arXiv. [arXiv]
10. Fülöp, Z. and Vogler, H. 1998. Syntax-Directed Semantics: Formal Models Based on Tree Transducers. Springer Berlin Heidelberg. [doi]
11. Gécseg, F. and Steinby, M. 1997. Tree Languages. Handbook of Formal Languages, 1–68. [doi]
12. Gécseg, F. and Steinby, M. 2015. Tree Automata. arXiv. [arXiv]
13. Nivat, M. 1968. Transductions des langages de Chomsky. Annales de l’institut Fourier 18, 1, 339–455. [url]
14. Rounds, W.C. 1968. Trees, transducers and transformations. .
15. Rounds, W.C. 1970. Mappings and Grammars on Trees. Mathmatical Systems Theory 4, 3, 257–287. [doi]
16. Thatcher, J.W. 1970. Generalized² sequential machine maps. Journal of Computer and System Sciences 4, 4, 339–367. [doi]

Kontakt

• Prof. Dr.-Ing. habil. Dr. h.c./Univ. Szeged
  Heiko Vogler
  Tel.: +49 (0) 351 463-38232
• Dipl.-Inf. Tobias Denkinger
  Tel.: +49 (0) 351 463-38469