Aktuelle Hinweise

Die Übung am 11.12.2014 entfällt!

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.

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.

Stundenplan

• Vorlesung: Mo., 4.DS, APB/E009 (Beginn am 13.10.)
• Übung: Do., 5.DS, APB/E009 (Beginn am 16.10.)

Vorlesung

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.

Inhalte der einzelnen Vorlesungen

Literatur

• B.S. Baker. Composition of top-down and bottom-up tree transductions. Inform. and Control, 41(2):186–213, 1979.
• F. Baader and T. Nipkow. Term Rewriting and All That. Cambridge University Press, Cambridge, 1998.
• N. Dershowitz. Termination of Rewriting. J. Symbolic Comput., 3:69–116, 1987.
• N. Dershowitz and J.P. Jouannaud. Rewrite systems. In Jan van Leeuwen, editor, Handbook of Theoret. Comput. Sci., Vol. B, chapter 6, pages 243–320. Elsevier Science Publishers B.V., 1990.
• J. Engelfriet. Bottom-up and top-down tree transformations—a comparison. Math. Systems Theory 9(2), pp. 198–231 (1975).
• J. Engelfriet. Top–down tree transducers with regular look–ahead. Math. Systems Theory, 10:289–303, 1977.
• J. Engelfriet. Three hierarchies of transducers. Math. Systems Theory, 15(2):95–125, 1982.
• Z. Fülöp and H. Vogler. Syntax-directed semantics — Formal Models Based on Tree Transducers. Monogr. Theoret. Comput. Sci. EATCS Ser. Springer-Verlag, 1998.
• F. Gécseg and M. Steinby. Tree Automata. Akadémiai Kiadó, Budapest, 1984.
• F. Gécseg and M. Steinby. Tree languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, chapter 1, pages 1–68. Springer-Verlag, 1997.
• M. Nivat. Transduction des langages de Chomsky. Ann. de l’Inst. Fourier, 18:339–456, 1968.
• W.C. Rounds. Trees, transducers and transformations. PhD thesis, Stanford University, 1968.
• W.C. Rounds. Mappings and grammars on trees. Math. Systems Theory, 4(3):257–287, 1970.
• J.W. Thatcher. Generalized² sequential machine maps. J. Comput. System Sci., 4(4):339– 367, 1970.

In den meisten Fällen lässt sich die Literatur aus dem Uni-Netz heraus gebührenfrei herunterladen. Zur Einführung eignet sich besonders "Bottom-up and top-down tree transformations" von J. Engelfriet.

Übung

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

Aufgaben

Die Aufgaben bitte vorbereiten. Ausgewählte Aufgaben werden dann auf Wunsch in der Übung besprochen.

• 1. Übungsblatt am 16. 10.
• 2. Übungsblatt am 23. 10.
• 3. Übungsblatt am 30. 10.
• 4. Übungsblatt am 06. 11.
• 5. Übungsblatt am 13. 11.
• 6. Übungsblatt am 20. 11.
• 7. Übungsblatt am 04. 12.
• Übung am 11. 12. fällt aus!
• 8. Übungsblatt am 17. 12.
• 9. Übungsblatt am 07. 01.
• 10. Übungsblatt am 14. 01.
• 11. Übungsblatt am 22. 01.
• 12. Übungsblatt am 29. 01.