Logik in der Informatik Prof. Dr. Nicole Schweikardt

Aktuelles

• Der ursprünglich für den 24.01.2018 angesetzte Vortrag wird auf den 31.01.2018 verschoben; am 24.01. gibt es stattdessen einen Vortrag über den Satz von Courcelle.
• Die Vorbesprechung, Themenvergabe und Festlegung weiterer Termine findet in der zweiten Vorlesungswoche, am Mittwoch, den 25.10.2017, um 15:30-17:00 Uhr in Raum 3.408 (Johann von Neumann-Haus) statt.
• In diesem Semester beschäftigt sich das Seminar mit dem Thema Algorithmische Metatheoreme.

Einführung

Anhand von Originalarbeiten und ergänzender Literatur werden im Seminar aktuelle Themen der Logik und Komplexität erarbeitet.

Ziele sind das Kennenlernen neuer Forschungsergebnisse, 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 Logik und Komplexität spezialisieren wollen. Die Teilnahme am Seminar setzt Kenntnisse, die in den Vorlesungen "Logik in der Informatik", "Logik und Komplexität", "Einführung in die Komplexitätstheorie" oder "Einführung in die Datenbanktheorie" vermittelt werden, voraus.

Ort und Zeit

Zeit und Raum

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

 

Veranstalter/in

Prof. Dr. Nicole Schweikardt

Vorträge

Mögliche Vortragsthemen

1. Der Satz von Courcelle: Linearzeit Model-Checking von MSO-definierbaren Eigenschaften baumartiger Strukturen
   Literatur: Kapitel 3 "Monadic Second-Order Logic on Tree-like Structures" (Seiten 16-30) der Arbeit Algorithmic Meta-Theorems von Stephan Kreutzer. Electronic Colloquium on Computational Complexity (ECCC) 16: 147 (2009)
   Originalarbeit: Graph Rewriting: An Algebraic and Logic Approach von Bruno Courcelle. In: Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B) 1990: 193-242
2. Der Satz von Bodlaender: Ein effizienter Algorithmus zum Erzeugen von Baumzerlegungen
   Literatur: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth von Hans L. Bodlaender. SIAM J. Comput. 25(6): 1305-1317 (1996)
3. Ein Resultat von Elberfeld, Jakoby und Tantau: Logspace-Versionen der Sätze von Courcelle und Bodlaender
   Literatur: Logspace Versions of the Theorems of Bodlaender and Courcelle von Michael Elberfeld, Andreas Jakoby, Till Tantau. Electronic Colloquium on Computational Complexity (ECCC) 18: 128 (2011) (dies ist die ausführliche Version einer in Proc. FOCS 2010: 143-152 erschienenen Arbeit)
4. Ein Resultat von Frick und Grohe: Effizientes Model-Checking von FO-definierbaren Eigenschaften von Strukturen mit lokal beschränkter Baumweite
   Literatur: Deciding first-order properties of locally tree-decomposable structures von Markus Frick und Martin Grohe. Journal of the ACM 48(6): 1184-1206 (2001)
5. Weitere Resultate von Frick: Effiziente Algorithmen für verallgemeinerte Model-Checking Probleme auf baumartigen Strukturen
   Literatur: Generalized Model-Checking over Locally Tree-Decomposable Classes von Markus Frick. Theory Comput. Syst. 37(1): 157-191 (2004)

Spielregeln

1. Rechtzeitige Vereinbarung und Wahrnehmung eines Sprechstundentermins, der mindestens 1 Woche vor dem eigenen Seminarvortrag stattfindet und während dem ein detailliertes Vortragskonzept inkl. Vortragsfolien/Tafellayout vorgelegt wird,
2. einen Vortrag zu einem der oben genannten Themen zu halten (Dauer: 60 Minuten, plus 10 Minuten zur Diskussion und zur Klärung von Fragen aus dem Publikum),
3. Anwesenheit an mind. 75% aller Vorträge und
4. Abgabe einer schriftlichen Ausarbeitung des Vortragsthemas: Länge ca 5 Seiten (mindestens 4, maximal 7), Layout wie in der Layout-Vorlage angegeben, Deadline: Ende der Vorlesungszeit des Wintersemesters 2017/18 (also: 17.02.2018, 23:59 Uhr), als pdf-Datei per Email zu senden an Prof. Dr. Nicole Schweikardt.