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

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. [doiurl]
  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
    Fax: +49 (0) 351 463-37959
  • Dipl.-Inf. Tobias Denkinger
    Tel.: +49 (0) 351 463-38469
    Fax: +49 (0) 351 463-37959
Stand: 12.01.2018 08:21 Uhr