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

Formale Übersetzungsmodelle im Wintersemester 2016/2017

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
  • Donnerstags, 5. DS (14:50–16:20 Uhr), APB/E009: Übung

Vorlesung

  • 2016-10-10: trees (basic notions, definition by structural induction, characteristics of trees)
  • 2016-10-17: tree transformations; from string transducers to tree transducers; bottom-up tree transducers (syntax, semantics, some examples)
  • 2016-10-24: non-determinism followed by copying (B1), checking followed by deletion (B2), decomposition of derivations, syntactic subclasses of BOT
  • 2016-11-07: recognizable tree languages, powerset construction (FTA = dt-FTA), decompositions of (l-)BOT (BOT ⊆ REL ; FTA ; HOM, l-BOT ⊆ REL ; FTA ; l-HOM, and BOT ⊆ QREL ; HOM)
  • 2016-11-14: closure of (l-)BOT under FTA (BOT ; FTA ⊆ BOT and l-BOT ; FTA ⊆ l-BOT)
  • 2016-11-21: closure of (l-)BOT under HOM (BOT ; HOM ⊆ BOT and l-BOT ; l-HOM ⊆ l-BOT), regular tree grammars, closure of REC under l-BOT
  • 2016-11-28: dom(BOT) is recognizable, syntax and semantics of top-down tree transducers, copying followed by nondeterminism, deletion followed by partialness, decomposition of derivations of td-tts, syntactic subclasses of TOP, representation of right-hand sides
  • 2016-12-05: decomposition of TOP (TOP ⊆ h-TOP ; l-TOP), ln-TOP = ln-BOT
  • 2016-12-12: h-TOP = HOM and r-TOP = REL, l-TOP ⊊ l-BOT
  • 2016-12-19: BOT and TOP are incomparable
  • 2017-01-09: nonclosure of BOT and TOP under composition, Baker's theorem for BOT
  • 2017-01-16: Baker's theorem for TOP, l-BOT is closed under composition and other corollaries, top-down tree transducers with regular look-ahead (idea, syntax)
  • 2017-01-23: TOPR ⊆ d-QREL ; TOP, l-BOT = l-TOPR, a Hasse diagram

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

  • 2016-10-13: Übungsblatt 1 (ranked alphabets and trees, definition by structural induction)
  • 2016-10-20: Übungsblatt 2 (proof by structural induction, gsms and bu-tts, relabeling and checking)
  • 2016-10-27: Übungsblatt 3 (shape-preserving tree transformations, non-determinism and determinism, syntactic subclasses of BOT)
  • 2016-11-03: keine Übung
  • 2016-11-10: Übungsblatt 4 (powerset construction, bounded growth property, BOT ⊆ REL ; FTA ; HOM, BOT ⊆ QREL ; HOM)
  • 2016-11-17: Übungsblatt 5 (relabeling followed by checking, bimorphism characterization of BOT)
  • 2016-11-24: Übungsblatt 6 (BOT ; HOM ⊆ BOT, regular tree grammars)
  • 2016-12-01: Übungsblatt 7 (symbolic derivation), Tiburon can be found here, a tutorial is provided on this page
  • 2016-12-08: Übungsblatt 8 (ln-TOP = ln-BOT, gsms and td-tts)
  • 2016-12-15: Übungsblatt 9 (h-TOP = HOM and r-TOP = REL, l-TOP ⊊ l-BOT)
  • 2017-01-05: Übungsblatt 10 (tree transducers and finite state automata)
  • 2017-01-12: Übungsblatt 11 (BOT² and TOP², Baker's theorem for BOT)
  • 2017-01-19: Übungsblatt 12 (Baker's theorem for TOP, top-down tree transducer with regular look-ahead)
  • 2017-01-26: Übungsblatt 13 ((l-)TOPR ⊆ d-QREL ; (l-)TOP, l-BOT = l-TOPR)

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: 30.08.2017 12:29 Uhr