Logik in der Informatik Prof. Dr. Nicole Schweikardt

Aktuelles

• Am 12.02.15 ab 11h15 findet in Raum 3.408 ein Vortrag von Prof. Leonid Libkin (Univ. of Edinburgh) zum Thema "Incomplete Data: What Went Wrong, and How to Fix It" statt. Interessenten sind herzlich eingeladen! Die Vortragsankündigung findet sich hier.

• Am 19.11.14 ab 13h15 findet ein Vortrag zu Thema 3 statt.
• Die Vorbesprechung, Themenvergabe und Festlegung weiterer Termine fand in der zweiten Vorlesungswoche, am Mittwoch, den 22.10.2014, um 13:15-15:00 Uhr in Raum 3.408 (Johann von Neumann-Haus) statt.
• In diesem Semester werden wir uns das Thema der effizienten Aufzählung von Datenbank-Anfrageergebnissen anhand von aktuellen Originalarbeiten genauer anschauen.

Einführung

Anhand von Originalarbeiten und ergänzender Literatur werden im Seminar aktuelle Themen der Theoretischen Informatik, insbesondere der Logik, Datenbanktheorie und Komplexitätstheorie erarbeitet.

Ziele sind das Kennenlernen neuer Forschungsergebnisse der Theoretischen Informatik, das Verstehen wissenschaftlicher Originaltexte, die Fähigkeit zur Einordnung der Inhalte und Beweistechniken, sowie deren Wiedergabe in eigener Darstellung in einem begrenzten Zeitrahmen.

Das Seminar richtet sich an fortgeschrittene Studierende in einem Diplom- oder Masterstudiengang, die sich im Bereich Theoretische Informatik spezialisieren wollen. Die Teilnahme am Seminar setzt sehr gute und zumindest in einem Bereich auch tiefergehende Kenntnisse der Theoretischen Informatik voraus.

Koordinaten

Zeit und Raum

Mittwochs, 13:15-15:00 Uhr im Johann von Neumann-Haus (Rudower Chaussee 25), Raum 3.408

 

Veranstalterin

Prof. Dr. Nicole Schweikardt

Mögliche Vortragsthemen

1. First-order queries on structures of bounded degree are computable with constant delay. Arnaud Durand, Etienne Grandjean. ACM Trans. Comput. Log. 8(4), 2007.
   Insbes.: Kapitel 1, Kapitel 2.1 ohne 2.1.1, Kapitel 2.2, Kapitel 3.1 und 3.2.
2. First-order query evaluation on structures of bounded degree. Wojciech Kazana, Luc Segoufin. Logical Methods in Computer Science 7(2), 2011.
3. Enumerating answers to first-order queries over databases of low degree. Arnaud Durand, Nicole Schweikardt, Luc Segoufin. Proc. PODS 2014, pages 121-131.
4. On Acyclic Conjunctive Queries and Constant Delay Enumeration. Guillaume Bagan, Arnaud Durand, Etienne Grandjean. Proc. CSL 2007, pages 208-222.
5. Efficient Enumeration for Conjunctive Queries over X-underbar Structures. Guillaume Bagan, Arnaud Durand, Emmanuel Filiot, Olivier Gauwin. Proc. CSL 2010, pages 80-94.
6. Enumeration Complexity of Logical Query Problems with Second-order Variables. Arnaud Durand, Yann Strozecki. Proc. CSL 2011, pages 189-202.
7. Enumeration of monadic second-order queries on trees. Wojciech Kazana, Luc Segoufin. ACM Trans. Comput. Log. 14(4): 25, 2013.
8. MSO queries on trees: enumerating answers under updates. Katja Losemann, Wim Martens. Proc. CSL-LICS 2014, acrticle no. 67.