Seminar über Automaten für XML

» Diese Veranstaltung wird auf deutsch gehalten.

Seminar im Wintersemester 2005/2006

ArtTermine/OrtVeranstalter
S2 Di 16:00 - 19:00 Seminarraum I1 Thomas, Löding, Karianto, Rohde, Wöhrle

Inhalt

Gegenstand dieses Seminars sind Originalarbeiten und Überblicksartikel zur Verarbeitung von XML-Dokumenten mit automatentheoretischen Mitteln, mit einem Schwerpunkt im Umkreis der Vorlesungen Advanced Theory of Finite Automata und Unendliche Transitionssysteme des SS 2005. Aktive Teilnahme an (wenigstens) einer dieser Vorlesungen inklusive Übungen ist hilfreich zur Bearbeitung der Themen und wird bei der Zuteilung von Plätzen berücksichtigt.

Die Vorbesprechung mit Themenvergabe und Erläuterungen zum Ablauf findet am Ende der Vorlesungszeit statt und ist für alle Teilnehmer verpflichtend. Die zugelassenen Teilnehmer erhalten per E-Mail gesondert Nachricht.

Themen und Termine

Aufgrund der hohen Teilnehmerzahl findet das Seminar an 10 Terminen mit jeweils zwei Vorträgen statt (jeweils dienstags ab 16 Uhr). Bitte beachten Sie, dass das die Vorträge im Seminarraum des Lehrstuhls I (E1, Ergeschoss) stattfinden.

Die Literaturangaben sind noch nicht vollständig und dienen nur zur Orientierung. Die meisten der angegebenen Links verweisen auf Seiten, auf denen die angegebenen Artikel in elektronischer Form verfügbar sind. Die genauen Literaturangaben erfahren Sie von Ihrem Betreuer.

Automatentheoretische Grundlagen und Beschreibungssprachen

18.10.2005: Zweiwege-Automaten über Wörtern
Vortragende: Paul Hänsch, Nils Jeners
Betreuer: W. Thomas
Literatur:

  1. D. Kozen. Lecture 18 und Exercise 61 aus Automata and Computability, Springer 1997. Link

    M. Vardi. A note on the reduction of two-way automata to one-way automata, Inf. Proc. Lett. 30 (1989), 261-264. Link

  2. W.J. Sakoda, M. Sipser. Nondeterminism and the size of two-way automata, Proc. 10th ACM Symp. on Theory of Computing, 275-286, 1967.
25.10.2005: Tree- und Grid-Walking-Automaten
Vortragende: Ray Bohnenberger, Wladimir Fridman
Betreuer: W. Thomas
Literatur:
  1. M. Blum, C. Hewitt. Automata on a 2-dimensional tape, Proc. 8th IEEE Symp. on Switching and Automata Theory, 155-167, 1967.
  2. J. Engelfriet, H.J. Hoogeboom, J.-P. van Best. Trips on trees, Acta Cyb. 14 (1999), 51-64. Link
08.11.2005: Hedge- und Caterpillar-Automaten
Vortragende: Sasa Belak, Sven Hendriks
Betreuer: Ph. Rohde, W. Karianto
Literatur:
  1. A. Brüggemann-Klein, M.Murata, and D. Wood. Regular tree and regular hedge languages over unranked alphabets. Technical Report HKTUST-TCSC-2001-05, HKUST Theoretical Computer Science Center Research, 2001. Link
  2. Anne Brüggemann-Klein, Derick Wood, Caterpillars: A Context Specification Technique (2000). Link
15.11.2005: Top-Down-Baumautomaten, DTDs mit einfachen regulären Ausdrücken
Vortragende: Christoph Zymla, Mark Wiesemann
Betreuer: Ph. Rohde
Literatur:
  1. Julien Cristau, Top-down tree automata over XML trees. PostScript-Datei
  2. Wim Martens, Frank Neven and Thomas Schwentick. Complexity of Decision Problems for Simple Regular Expressions. In Proc. 29th Symposium on Mathematical Foundations of Computer Science (MFCS 2004), pages 889-900, 2004. Link
22.11.2005: XML-Schemas
Vortragende: Yvonne Jansen, Yingying Zhang
Betreuer: W. Karianto
Literatur:
  1. Silvano Dal Zilio, Denis Lugiez. XML Schema, Tree Logic and Sheaves Automata. Rapport de recherche de l'INRIA. Link

Anfragesprachen und Anfrageauswertung

29.11.2005: XPath
Vortragende: Michael Gerber, André Kolbe
Betreuer: S. Wöhrle
Literatur:

  1. W3C Recommendation XML Path Language (XPath) Link

    Georg Gottlob, Christoph Koch, und Reinhard Pichler. Efficient Algorithms for Processing XPath Queries. In Proc. VLDB 2002. Link

  2. Peter Buneman, Martin Grohe, und Christoph Koch Path Queries on Compressed XML. In Proc. VLDB 2003. Link
06.12.2005: Anfrage-Automaten, monadisches Datalog
Vortragende: Florian Koch, Frank Radmacher
Betreuer: S. Wöhrle
Literatur:
  1. Frank Neven, Thomas Schwentick. Query Automata. TCS 2002 Link
  2. G. Gottlob, C. Koch. Monadic datalog and the expressive power of languages for web information extraction. Journal of the ACM, 51(1):74-113, January 2004. Link
13.12.2005: Binäre Anfragen, Anfragen mit numerischen Bedingungen
Vortragende: Frank Pöttgen, Bodo Felger
Betreuer: Ph. Rohde, W. Karianto
Literatur:
  1. Alexandru Berlea und Helmut Seidl. Binary Queries. Extreme Markup Languages, 2002 Conference, Montreal, August 2002. Link
  2. Helmut Seidl, Thomas Schwentick and Anca Muscholl. Numerical document queries. In Proc. 22nd Symposium on Principles of Database Systems (PODS 2003), 155-166. Link

Transformationen, Typechecking und Streaming

17.01.2006: Baum-Transducer und Typechecking
Vortragende: Jun Park, Roman Rabinovich
Betreuer: Ch. Löding
Literatur:
  1. Kapitel 6 des Buches Tree Automata Techniques and Applications. Link
  2. Tova Milo, Dan Suciu, Victor Vianu, Typechecking for XML Transformers Published in Journal of Computer and System Science, 2002 Link
24.01.2006: Anfragen und Validierung für XML-Streams
Vortragende: Daniel Neider, Martin Kappe
Betreuer: Ch. Löding
Literatur:
  1. Luc Segoufin, Victor Vianu. Validating Streaming XML Documents. (PODS'02) Link
  2. Christoph Koch und Stefanie Scherzinger. Attribute Grammars for Scalable Query Processing on XML Streams. In Proc. DBPL 2003. Link