Logik in der Informatik
Prof. Dr. Martin Grohe

Automaten und semistrukturierte Daten (XML)

Aktuelles Einführung Zeit & Raum Literatur Vortragsthemen Vorträge Programm Ausarbeitungen

Aktuelles

An dieser Stelle finden Sie im Laufe des Seminars aktuelle Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt.

Programm

Das Seminar findet in Raum 1'308 des Erwin-Schrödinger-Zentrums statt und beginnt um 9:00 Uhr s.t.
Für jeden Vortrag sind 45 Minuten plus 10-15 Minuten für die anschließende Diskussion eingeplant.
Die Ausarbeitungen der einzelnen Vortragsthemen finden Sie hier.

Donnerstag, 24.02.05

9:00 - 10:00: Bettina Hepp, Baumautomaten und Monadische Logik zweiter Stufe auf binären Bäumen
10:00 - 11:00: Stephan Seigewasser, Reguläre Baum- und Hedge-Sprachen über unbeschränkten Alphabeten
11:00 - 11:15: kurze Pause
11:15 - 12:15: Yvonne Fischer, Anfrage-Automaten über endlichen Bäumen von beschränktem Grad
12:15 - 13:15: Alexandra Rostin, Anfrage-Automaten über endlichen Bäumen von unbeschränktem Grad
13:15 - 14:15: Mittagspause
14:15 - 15:15: Peter Laufer, Monadisches Datalog
15:15 - 16:15: Evgeniya Ershova, Bearbeitung von XML-Strömen mit deterministischen Automaten
16:15 - 16:30: kurze Pause
16:30 - 17:30: Matthias Schmidt, XML Attributgrammatiken

Freitag, 25.02.05

9:00 - 10:00: Stefan Deumlich, XSLT - Ein formales Modell
10:00 - 11:00: Marco Oppel, Validierung von XML-Strömen
11:00 - 11:15: kurze Pause
11:15 - 12:15: Andreas Müller, Typüberprüfung von XML-Transformationen
12:15 - 13:15: Mittagspause
13:15 - 14:15: Jakob Voß, Tree-Walking Automaten
14:15 - 15:15: Andreas Meyer, Tree-Walking Automaten können nicht determinisiert werden

Einführung

Automatentheoretische Methoden spielen eine vielfältige und sehr nützliche Rolle bei der Bearbeitung von semistrukturierten Daten. Zum einen lassen sich Schemainformation (d.h. Information über die Struktur), wie sie für XML etwa in Form von DTDs oder XML-Schema Spezifikationen vorliegen, mit Baumautomaten beschreiben und algorithmisch bearbeiten. Zum anderen bieten automatentheoretische Techniken vor allem speichereffiziente Verfahren zur Ausführung von Anfragen an sehr große XML-Dokumente.

Im Seminar werden Originalarbeiten und Buchabschnitte zum Thema behandelt. Vorausgesetzt werden gute Kenntnisse der theoretischen Informatik. Grundlegende Kenntnisse der Datenbanktheorie oder die Teilnahme an einer der Vorlesungen "Logik und Komplexität" oder "Logiken, Spiele und Automaten" sind sicherlich hilfreich, aber nicht unbedingt erforderlich.

Zeit und Raum

Das Seminar ist als Blockseminar organisiert und findet am 24.2 und 25.2.2005 jeweils ab 9:00 Uhr in Raum 1'308 des Erwin-Schrödinger-Zentrums statt.
Eine Vorbesprechung findet in der ersten Semesterwoche am Freitag, dem 22.10.2004, um 13:00 im Raum 4.410, Johann von Neumann Haus (RUD 25) statt.

Einführende Literatur

Der folgende Artikel ist obligatorischer Lesestoff für alle Seminarteilnehmer/innen:

[KSS]

Nils Klarlund, Thomas Schwentick and Dan Suciu.
XML: Model, Schemas, Types, Logics, and Queries.
In Logics for Emerging Applications of Databases, Springer-Verlag, 2004, Seite 1-41.

Weitere Informationen finden sich (neben den u.g. Artikeln zu den einzelnen Vorträgen) in:

[Nev02]	Frank Neven. Automata, Logic, and XML. Proceedings CSL'02, pp 2-26.
[Th73]	James W. Thatcher. Tree automata: An informal survey. In: A. Aho (Ed.), Comments in the theory of computing, Prentice-Hall, 1973, pp 143-172.
[CDG+]	H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi. Tree Automata Techniques and Applications. Verfügbar unter http://www.grappa.univ-lille3.fr/tata.
[ABS]	S. Abiteboul, P. Buneman und D. Suciu. Data on the Web. Morgan Kaufmann, San Francisco, CA, 2000.

Vortragsthemen

I. Klassische Theorie der Baumautomaten und Logik (MSO-Logik)

I.1.	t.b.a.
I.2.	Anne Brüggemann-Klein, Makoto Murata, Derick Wood. Regular tree and regular hedge languages over unranked alphabets. HKUST Theoretical Computer Science Center Research Report, HKUST-TCSC-2001-05.

II. Anfragebearbeitung

II.1.	Frank Neven und Thomas Schwentick. Query automata over finite trees. Theoretical Computer Science 275(1-2): 633-674 (2002).
II.2.	Georg Gottlob und Christoph Koch. Monadic datalog and the expressive power of languages for Web information extraction. Journal of the ACM 51(1): 74-113 (2004).
II.3.	Christoph Koch. Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach. Proceedings VLDB'03: pp 249-260. Zum Thema "STAs" auch den entsprechenden Abschnitt in der folgenden Arbeit beachten: Markus Frick, Martin Grohe, Christoph Koch: Query Evaluation on Compressed Trees. Proceedings LICS'03. Beispiele und den Programmcode gibt es unter http://www.dbai.tuwien.ac.at/staff/koch/arb/.
II.4.	Todd J. Green, Gerome Miklau, Makoto Onizuka, Dan Suciu: Processing XML Streams with Deterministic Automata. Proceedings ICDT'03: pp 173-189. Für Details siehe auch die Zeitschriftenversion: Todd J. Green, Ashish Gupta, Gerome Miklau, Makoto Onizuka, Dan Suciu. Processing XML Streams with Deterministic Automata and Stream Indexes. ACM TODS, vol. 29, no. 4, December 2004.
II.5.	Christoph Koch und Stefanie Scherzinger. Attribute Grammars for Scalable Query Processing on XML Streams. Proceedings DBPL'03: pp 233-256
II.6.	Geert Jan Bex, Sebastian Maneth, Frank Neven. A formal model for an expressive fragment of XSLT. Information Systems 27(1): 21-39 (2002).

III. Schema-Sprachen und Validierung

III.1.	Dongwon Lee, Murali Mani, Makoto Murata. Reasoning about XML Schema Languages using Formal Language Theory. Technical Report, IBM Almaden Research Center, RJ# 10197, Log# 95071, 37 Seiten, Nov. 2000.
III.2.	Luc Segoufin und Victor Vianu. Validating Streaming XML Documents. Proceedings PODS'02: 53-64.

IV. Typüberprüfung

IV.1.	Tova Milo, Dan Suciu, Victor Vianu. Typechecking for XML Transformers. J. Comput. Syst. Sci. 66(1): 66-97 (2003).
IV.2.	Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu. XML with data values: typechecking revisited. J. Comput. Syst. Sci. 66(4): 688-727 (2003).

V. Tree-Walking Automaten

V.1.	Frank Neven und Thomas Schwentick. On the power of tree-walking automata. Information and Computation 183 (2003), pp 86-103.
V.2.	Mikolaj Bojanczyk und Thomas Colcombet. A Regular Tree Language Not Recognized by Any Tree-Walking Automaton. Manuskript, Juli 2004, 51 Seiten.

Vorträge

Thema	Vortragende/r	Ansprechpartner
I.1	Bettina Hepp	Martin Grohe
I.2	Stephan Seigewasser	Martin Grohe
II.1 (erste Hälfte)	Yvonne Fischer	Nicole Schweikardt
II.1 (zweite Hälfte)	Alexandra Rostin	Nicole Schweikardt
II.2	Peter Laufer	Martin Grohe
II.4	Evgeniya Ershova	Nicole Schweikardt
II.5	Matthias Schmidt	Nicole Schweikardt
II.6	Stefan Deumlich	Nicole Schweikardt
III.2	Marco Oppel	Nicole Schweikardt
IV.1	Andreas Müller	Martin Grohe
V.1	Jakob Voß	Martin Grohe
V.2	Andreas Meyer	Martin Grohe

Last modified: Mon Feb 28 15:14:07 CET 2005
Nicole Schweikardt

Automaten und semistrukturierte Daten (XML)

Aktuelles

Programm

Einführung

Zeit und Raum

Einführende Literatur

Vortragsthemen

I. Klassische Theorie der Baumautomaten und Logik (MSO-Logik)

I.1.

I.2.

II. Anfragebearbeitung

II.1.

II.2.

II.3.

II.4.

II.5.

II.6.

III. Schema-Sprachen und Validierung

III.1.

III.2.

IV. Typüberprüfung

IV.1.

IV.2.

V. Tree-Walking Automaten

V.1.

V.2.

Vorträge