Seminar über Baumautomaten

» Diese Veranstaltung wird auf deutsch gehalten.

Seminar im Wintersemester 2007/2008

ArtTermine/OrtVeranstalter
S2 01.02.2008 4116
08.02.2008 4116		 Thomas, Löding, Holtmann, Karianto, Radmacher

Allgemeine Informationen

Das Seminar ist als Blockseminar an zwei Terminen in den letzten zwei Wochen der Vorlesungszeit geplant.

Inhalt

Ziel des Seminars ist die Vertiefung der Theorie der Baumautomaten, deren Grundlagen in der Vorlesung Angewandte Automatentheorie aus dem Sommersemester 2007 behandelt wurden. Basierend auf dem elektronischen Buch TATA: Tree Automata Techniques and Applications und einigen Originalarbeiten sollen erweiterte Automatenmodelle und zum Teil deren Anwendungen (z.B. XML, kryptographische Protokolle) studiert werden.

Stichworte zu den behandelten Themen sind:
  • Automaten mit Vergleichsoperationen
  • Baumtransformationen
  • Alternierende Baumautomaten
  • Automaten für ungeordnete Bäume

Anmeldung und Vorbesprechung

Die Vergabe der Plätze erfolgt zentral.

Die Anmeldung ist abgeschlossen. Es sind alle Plätze vergeben.

Wir empfehlen eine Anmeldung nur dann, wenn bereits eine Vorlesung besucht wurde, in der die Grundlagen der Theorie der Baumautomaten behandelt wurden (wie z.B. in Angewandte Automatentheorie).

Die Vorbesprechung mit Themenvergabe und Erläuterungen zum Ablauf findet am 09.02.2007 ab 9 Uhr im Seminarraum am Lehrstuhl 7 statt und ist für alle Teilnehmer verpflichtend. Die zugelassenen Teilnehmer erhalten per E-Mail gesondert Nachricht.

Vorträge und Termine

  1. Pfadorientierte Baumautomaten
    Termin: 01.02.2008, 08:30-09:30
    Vortrag: Stefan Breuer
    Betreuer: F. Radmacher
    Quellen: [MSS06]
  2. Relationen über Bäumen
    Termin: 01.02.2008, 09:30-10:30
    Vortrag: Neda Nazari
    Betreuer: F. Radmacher
    Quellen: [TATA, Kap. 3]
  3. Kontextfreie Baumsprachen
    Termin: 01.02.2008, 10:50-11:50
    Vortrag: Farhad Soleimankhani
    Betreuer: M. Holtmann
    Quellen: [SG85]
  4. Baumautomaten mit Unterbaumvergleichen
    Termin: 01.02.2008, 11:50-12:50
    Vortrag: Gatsioudis Ioannis
    Betreuer: W. Karianto
    Quellen: [TATA, Kap. 4]
  5. Baumautomaten mit Speicher
    Termin: 01.02.2008, 14:00-15:00
    Vortrag: Christian Werner
    Betreuer: W. Karianto
    Quellen: [CJP07]
  6. Lernen regulärer Baumsprachen
    Termin: 01.02.2008, 15:00-16:00
    Vortrag: Sebastian Pick
    Betreuer: C. Löding
    Quellen: [DH03,BM04]
  7. Set Constraints
    Termin: 08.02.2008, 08:30-09:30
    Vortrag: Björn Wolf
    Betreuer: C. Löding
    Quellen: [TATA, Kap. 5]
  8. Automaten für unbeschränkt verzweigte Bäume
    Termin: 08.02.2008, 09:30-10:30
    Vortrag: Max Wilke
    Betreuer: C. Löding
    Quellen: [TATA, Kap. 8]
  9. Eindeutige reguläre Ausdrücke für DTDs
    Termin: 08.02.2008, 10:50-11:50
    Vortrag: Jörg Fiedler
    Betreuer: M. Holtmann
    Quellen: [BW98]
  10. Typisierung linearisierter XML-Dokumente
    Termin: 08.02.2008, 11:50-12:50
    Vortrag: Markus Vervier
    Betreuer: C. Löding
    Quellen: [MNS04]
  11. Automaten für ungeordnete Bäume
    Termin: 08.02.2008, 14:00-15:00
    Vortrag: Daniel Götten
    Betreuer: W. Thomas
    Quellen: [SSM03]
  12. Equational Tree Automata
    Termin: 08.02.2008, 15:00-16:00
    Vortrag: Christoph Wollgarten
    Betreuer: C. Löding
    Quellen: [Ohs01],[HOV06]

Quellen

[AAT] W. Thomas Angewandte Automatentheorie. Skript zur Vorlesung. Webseite
[BM05] J. Besombes, J.-Y. Marion. Learning Tree Languages from Positive Examples and Membership Queries. Algorithmic Learning Theory, 15th International Conference, ALT 2004, Padova, Italy, October 2-5, 2004, Proceedings Lecture Notes in Computer Science 3244, pp. 440-453, Springer, 2004.
[BW98] A. Brüggemann-Klein, D. Wood One-unambiguous regular languages Information and Computation 140(2), pp 229 - 253, 1998
[CJP07] H. Comon-Lundh, F. Jacquemard, N. Perrin Tree Automata with Memory, Visibility and Structural Constraints Research Report LSV-07-01, 2007.
[Cri04] J. Cristau Top-down tree automata over XML trees. Internal Research Report. 2004
[DH03] F. Drewes, J. Högberg Learning a Regular Tree Language from a Teacher. Developments in Language Theory, 7th International Conference, DLT 2003 Lecture Notes in Computer Science 2710, pp. 279-291, Springer, 2003.
[HOV06] J. Hendrix, H. Ohsaki, M. Viswanathan Propositional Tree Automata. Term Rewriting and Applications, 17th International Conference, RTA 2006, Seattle, WA, USA, August 12-14, 2006, Proceedings Lecture Notes in Computer Science 4098, pp. 50-65, Springer, 2006.
[MNS04] W. Martens, F. Neven, T. Schwentick. Which XML Schemas Admit 1-Pass Preorder Typing? Database Theory - ICDT 2005, Lecture Notes in Computer Science 3363, Springer, 2004.
[MSS06] A. Muscholl, M. Samuelides, L. Segoufin Complementing deterministic tree-walking automata. Information Processing Letters 99(1) pp. 33-39, 2006.
[Ohs01] H. Ohsaki Beyond Regularity: Equational Tree Automata for Associative and Commutative Theories. Computer Science Logic, 15th International Workshop, CSL 2001. 10th Annual Conference of the EACSL, Paris, France, September 10-13, 2001, ProceedingsLecture Notes in Computer Science 2142, pp. 539-553, Springer, 2001
[SG85] K.M. Schimpf, J.H. Gallier Tree Pushdown Automata Journal of Computer and System Sciences 30, pp 25-40, 1985
[SSM03] H. Seidl, T. Schwentick, A. Muscholl. Numerical document queries. Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pp. 155-166, ACM 2003
[TATA] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, M. Tommasi Tree Automata Techniques and Applications. Version from October 2007. Webseite