Uni des Saarlandes
FR Informatik
Programmiersysteme
Vorlesungen
Seminar SS-03

Logische Aspekte von XML

Seminar/Proseminar im Sommersemester 2003

Prof. Gert Smolka, Tim Priesnitz, Andreas Rossberg
Lehrstuhl für Programmiersysteme, FR Informatik, Universität des Saarlandes

VORBESPRECHUNG: Freitag, 25. April 2003, 13:30 Uhr, Geb. 45, Rm. 528

DURCHFÜHRUNG: Blockveranstaltung 8.-10. Oktober 2003

XML ist ein vom World Wide Web Consortium unterstütztes Format für den Austausch semi-struktukturierter Daten im Web. Im Zuge der Internet-Euphorie wurde XML oft als Wundermittel angepriesen. Aus technischer Sicht ist XML eine eher einfache Baumbeschreibungssprache, in deren Zusammenhang sich jedoch interessante Typ- und Anfragelogiken ergeben. Das Seminar soll die logischen Aspekte von XML beleuchten und in die dafür benötigten theoretischen Grundlagen einführen.

Programm

Mittwoch, 8. Oktober 2003
1. 10:00 - 10:30 Baeume als Datenmodelle Frank Schmidt (Ausarbeitung / Folien)
   • Serge Abiteboul, Peter Buneman and Dan Suciu. Data on the Web, Kapitel 2-3, Morgan Kaufmann, 2000.
   • Serge Abiteboul, Semistructured Data: from Practice to Theory, LICS 2001.
2. 10:30 - 11:00 Endliche Automaten Stoyan Mutafchiev (Ausarbeitung / Folien)
3. 11:00 - 12:00 Monadische Logik zweiter Stufe (MSO) Ilhan Aslan (Ausarbeitung / Folien)
   • Bakhadyr Khoussainov und Anil Nerode. Automata Theory and Its Applications , Birkhäuser, 2001.
   • Wolfgang Thomas. Languages, Automata and Logic (technical report version), Handbook on Formal Languages, Vol 3. Springer Verlag, 1997.
   • Hubert Comon et al., TATA, Kapitel 3, Online-Publikation.
Pause
4. 14:00 - 15:00 Baumautomaten Christian Klein (Ausarbeitung / Folien)
   • Hubert Comon et al., TATA, Online-Publikation.
5. 15:00 - 16:00 Korrespondenz zwischen Automaten & Logik Jens Kerber (Ausarbeitung / Folien)
   • Frank Neven, Automata, Logic, and XML, CSL 2002.
   • Wolfgang Thomas. Languages, Automata and Logic (technical report version), Handbook on Formal Languages, Vol 3. Springer Verlag, 1997.
   • Bakhadyr Khoussainov und Anil Nerode. Automata Theory and Its Applications , Birkhäuser, 2001.
   • Hubert Comon et al., TATA, Online-Publikation.
Donnerstag, 9. Oktober 2003
6. 10:00 - 10:30 MONA - Monadische Logik in der Praxis Martin Emrich (Ausarbeitung / Folien)
7. 10:30 - 11:30 Omega-Automaten Swen Jacobs (Ausarbeitung / Folien)
8. 11:30 12:00 Anfragen an XML-Dokumente Björn Gehl (Ausarbeitung / Folien)
   • Serge Abiteboul, Peter Buneman and Dan Suciu. Data on the Web, Kapitel 2-3, Morgan Kaufmann, 2000.
   • Serge Abiteboul, Semistructured Data: from Practice to Theory, LICS 2001.
Freitag, 10. Oktober 2003
9. 10:00 - 11:00 XML-Automaten Thomas Klöcker
   • Georg Gottlob und Christoph Koch, Monadic Datalog and the Exressive Power of Languages for Web Information Extraction. , PODS 2002.
   • Für Datalog: Serge Abiteboul, Richard Hull, Victor Vianu. Foundations of Databases, Kapitel 12, Addison-Wesley, 1995.
10. 11:00 - 12:00 XML-Schema Tobias Maurer (Ausarbeitung / Folien), Andreas Freier (Ausarbeitung / Folien),
    • (Betreuer: Andreas)
    • Jerome Simeon and Philip Wadler. The Essence of XML (ausgearbeitete Folien), POPL 2003.
11. 12:00 - 13:00 XML-Programmierung mit XDuce Daniel Beck (Ausarbeitung / Folien) Taoufik Romdhane (Ausarbeitung / Folien)
    • (Betreuer: Andreas)
    • Haruo Hosoya and Benjamin C. Pierce. XDuce: A typed XML processing language, ACM Transactions on Internet Technology, 2002.

Ausarbeitung

Zusätzliche Literatur und Links

• Philip Wadler, XML: Some hyperlinks minus the hype
• Diverse Papiere von F. Neven und T. Schwentick
• F. Neven and T. Schwentick, Query Automata on finite trees  Theoretical Computer, vol 275, 2002.
• Dagstuhl Seminar, Foundations of Semistructured Data
• Georg Gottlob und Christoph Koch, Monadic Queries over Tree-Structured Data. LICS 2002.

Voraussetzung für Scheinvergabe

• Anwesenheit zu den Seminarterminen
• Vortrag von 45min Länge plus Diskussion
• Schriftliche Ausarbeitung im Umfang von 10-15 Seiten (Abgabefrist wird bekannt gegeben)
• Elektronische Verfügbarkeit der Vortragsfolien und der schriftlichen Ausarbeitung (PDF, Postscript, oder Power Point)

Die Vortragsfolien sollten spätestens 2 Wochen vorher dem jeweiligen Betreuer vorgelegt werden.