Hauptregion der Seite anspringen
TU Dresden — Fakultät Informatik — Institut für Theoretische Informatik

Formale Übersetzungsmodelle im Wintersemester 2015/2016

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

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

Die letzte Vorlesung fand am 18.01.2016 statt.

Vorlesung

  • Vorlesung 1, 12.10.2015: trees, definition and proof by structural induction
  • Vorlesung 2, 19.10.2015: tree transformations, generalized sequential machines and tree transducer, bottom-up tree transducer (bu-tt), derivation relation of bu-tts
  • Vorlesung 3, 26.10.2015: non-determinism followed by copying, checking followed by deletion, composition and decomposition of derivations, syntactic classes of bu-tts, recognizable languages
  • Vorlesung 4, 02.11.2015: powerset construction for FTA
  • Vorlesung 5, 09.11.2015: BOT ⊆ REL ∘ FTA ∘ HOM
  • Vorlesung 6, 16.11.2015: (l)-BOT = REL ∘ FTA ∘ (l)-HOM
  • Vorlesung 7, 23.11.2015: top-down tree transducer (td-tt), derivation relation of td-tts, properties (T1) and (T2), composition and decomposition of derivations, syntactic classes of td-tts
  • Vorlesung 8, 30.11.2015: TOP ⊆ h-TOP ∘ l-TOP, ln-TOP = ln-BOT, h-TOP = HOM, r-TOP = REL
  • Vorlesung 9, 07.12.2015: l-TOP ⊊ l-BOT
  • Vorlesung 10, 14.12.2015: BOT and TOP are incomparable, neither BOT nor TOP is closed under composition
  • Vorlesung 11, 04.01.2016: Baker's theorem for the composition of bottom-up tree transducers
  • Vorlesung 12, 11.01.2016: Baker's theorem for the composition of top-down tree transducers, closure of HOM, REL, and FTA under composition, TOP = HOM ∘ l-TOP, l-BOT ∘ REL ⊆ l-BOT, l-BOT is closed under composition, BOTn ⊆ TOPn+1, TOPn ⊆ BOTn+1, l-BOT = l-TOP*, top-down tree transducer with regular look-ahead
  • Vorlesung 13, 18.01.2016: (l-)TOPR ⊆ d-QREL ∘ (l-)TOP, l-BOT = l-TOP, a Hasse diagram of tree transformation classes

Falls Sie diese Lehrveranstaltung in das Modul INF-PM-FOR einbringen möchten, einigen Sie sich bitte frühzeitig mit dem Prüfer über die dafür notwendigen 60 h Selbststudium.

Übungsaufgaben

Übungsblatt 13 schließt die Übungen ab.

Fragen zum Übungsbetrieb an Dipl.-Inf. Tobias Denkinger (vorname.nachname@tu-dresden.de).

Literatur

[Bak79] B.S. Baker. Composition of top-down and bottom-up tree transductions. Information and Control, Vol. 41(2), 186–213, 1979. DOI: 10.1016/S0019-9958(79)90561-8
[BN98] F. Baader and T. Nipkow. Term Rewriting and All That. Cambridge University Press, Cambridge, 1998. ISBN: 0-521-45520-0
[BPS61] Y. Bar-Hillel, M. Perles, and E. Shamir. On Formal Properties of Simple Phrase Structure Grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, Vol. 14, 1961.
[Der87] N. Dershowitz. Termination of Rewriting. Journal of Symbolic Computation, Vol. 3, 69–116, 1987. DOI: 10.1016/s0747-7171(87)80022-6
[DJ90] N. Dershowitz and J.P. Jouannaud. Rewrite systems. Handbook of Theoretical Computer Science, Vol. B, 243–320, 1990. ISBN: 0-444-88074-7, URL: http://dl.acm.org/citation.cfm?id=114897
[Eng75] J. Engelfriet. Bottom-up and top-down tree transformations—a comparison. Mathmatical Systems Theory, Vol. 9(2), 198–231, 1975. DOI: 10.1007/BF01704020
[Eng75a] J. Engelfriet. Tree automata and tree grammars. Lecture Note, Aarhus University, 1975. Siehe auch 2015, arXiv: 1510.02036
[Eng76] J. Engelfriet. Top-down tree transducers with regular look-ahead. Mathmatical Systems Theory, Vol. 10(1), 289–303, 1976. DOI: 10.1007/BF01683280
[Eng82] J. Engelfriet. Three hierarchies of transducers. Mathmatical Systems Theory, Vol. 15(1), 95–125, 1982. DOI: 10.1007/BF01786975
[FV98] Z. Fülöp and H. Vogler. Syntax-directed semantics: Formal Models Based on Tree Transducers. Monographs in Theoretical Computer Science An EATCS Series, 1998. DOI: 10.1007/978-3-642-72248-6
[GS84] F. Gécseg and M. Steinby. Tree Automata, 1st edition, Akadémiai Kiadó, 1984. ISBN: 963-05-3170-4. Siehe auch 2nd edition, 2015, arXiv: 1509.06233
[GS97] F. Gécseg and M. Steinby. Tree languages. Handbook of Formal Languages, Vol. 3, 1–68, 1997. DOI: 10.1007/978-3-642-59126-6_1
[Niv68] M. Nivat. Transduction des langages de Chomsky. Annales de l'institut Fourier, Vol. 18(1), 339–456, 1968. URL: http://eudml.org/doc/73950
[Rou68] W.C. Rounds. Trees, transducers and transformations. PhD thesis, Stanford University, 1968.
[Rou70] W.C. Rounds. Mappings and grammars on trees. Mathmatical Systems Theory, Vol. 4(3), 257–287, 1970. DOI: 10.1007/BF01695769
[Tha70] J.W. Thatcher. Generalized² sequential machine maps. Journal of Computer and System Sciences, Vol. 4(4), 339–367, 1970. DOI: 10.1016/s0022-0000(70)80017-4

In den meisten Fällen lässt sich die Literatur aus dem Uni-Netz heraus gebührenfrei herunterladen. Zur Einführung eignen sich besonders J. Engelfriet [Eng75] und [Eng75a]. Die Referenzen sind noch einmal in einer BIB-Datei zusammengefasst.

Stand: 16.10.2017 12:49 Uhr