Seminar Logik, Komplexität, Spiele: Algorithmische Meta-Theoreme in der Logik

WS 2016

Aktuelles

Das Seminar wird als Blockseminar angeboten. Die Vorträge finden im Seminarraum des Lehrstuhl statt (Raum 4116, E1, Ahornstr. 55) und können wahlweise auf Deutsch oder Englisch gehalten werden.

Zeitplan

07.11. Gliederung
05.12. 1. Version Ausarbeitung
02.01. finale Version Ausarbeitung
09.01. Folien
23.01. und 24.01. Vorträge

Einführungsliteratur

Folgende Übersichtsartikel sind für alle Themen als Einführungsliteratur empfohlen: [G08, K09, GK11]

Programm

Montag, 23. Januar
10:00 10:30 Marko van Treeck Fixed-parameter tractability
10:35 11:05 Oliver Feith Hierarchien in der parametrisierten Komplexitätstheorie
11:10 11:40 Lukas Rodenbüsch Varianten von monadischer Logik zweiter Stufe
13:00 13:30 Valentin Seiler Baumweite
13:35 14:05 Dimitri Rusin Der Satz von Courcelle
14:10 14:40 Johannes Rueben Cliquenweite
14:45 15:15 Jan-Frederik Konopka Lokalität von FO und der Satz von Seese
Dienstag, 24. Januar
11:00 11:30 Robert Lipp FO-Eigenschaften von Strukturen mit lokaler Baumzerlegung
13:00 13:30 Daniel Steenebrügge FO-Eigenschaften von nirgends dichten Graphen (1)
13:35 14:05 Nikolai von der Burg FO-Eigenschaften von nirgends dichten Graphen (2)
14:10 14:40 Katrin Dannert FO-Eigenschaften von nirgends dichten Graphen (3)
14:45 15:15 Yannic Rohde FO-Eigenschaften endlicher abelscher Gruppen entscheiden

Themen

Thema Vortragende(r) Betreuer(in) Literatur
Fixed-parameter tractability Marko van Treeck Matthias Hoelzel [FG06]
Hierarchien in der parametrisierten Komplexitätstheorie Oliver Feith Svenja Schalthöfer [FG06]
Varianten von monadischer Logik zweiter Stufe Lukas Rodenbüsch Svenja Schalthöfer [GHO00, C96, C03]
Baumweite Valentin Seiler Svenja Schalthöfer [B96, FG06]
Der Satz von Courcelle Dimitri Rusin Matthias Hoelzel [K09, G08]
Cliquenweite Johannes Rueben Matthias Hoelzel [K09, G08]
Lokalität von FO und der Satz von Seese Jan-Frederik Konopka Wied Pakusa [EF95, S95, K09]
FO-Eigenschaften von Strukturen mit lokaler Baumzerlegung Robert Lipp Frederic Reinhardt [FG01]
FO-Eigenschaften von nirgends dichten Graphen (1) Daniel Steenebrügge Wied Pakusa [S16, GKS14]
FO-Eigenschaften von nirgends dichten Graphen (2) Nikolai von der Burg Wied Pakusa [S16, GKS14]
FO-Eigenschaften von nirgends dichten Graphen (3) Katrin Dannert Wied Pakusa [S16, GKS14]
FO-Eigenschaften endlicher abelscher Gruppen entscheiden Yannic Rohde Frederic Reinhardt [Z16]
Mehr zur Komplexität von FO und MSO Lisa Mannel Frederic Reinhardt [FG04]

Literatur

Zuordnung

  • Informatik (B.Sc.)/Seminar Informatik
  • Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
  • Informatik (M.Sc.)/Seminar Theoretische Informatik
  • Mathematik (M.Sc.)/Seminar: Logik, Komplexität, Spiele (Reine Mathematik)
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/Modul Algebra
  • Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Voraussetzungen

  • Modul Mathematische Logik
  • für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Rückfragen

Erich Grädel, Svenja Schalthöfer, Matthias Hoelzel, Frederic Reinhardt, Wied Pakusa