Seminar Logik, Komplexität, Spiele: Fixpunktlogiken

SS 2009

Aktuelles

  • Die Seminarvorträge finden am 17. Juli statt.
  • Die Themen- und Betreuer-Zuteilung sowie ein vorläufiger Zeitplan stehen fest.
  • Als einführende Lektüre zum Thema Fixpunktlogiken und deskriptive Komplexität empfehlen wir Kapitel 3 aus Finite Model Theory and Its Applications [GKL+07].

Programm

Freitag, 17. Juli
10:00 10:45 Malte Nuhn Der modale μ-Kalkül
10:45 11:30 Vladislavs Serebro Inflationäre Fixpunkte in der Modallogik
11:30 11:45 Kaffeepause
11:45 12:30 Florian Weingarten Fixpunktlogik mit Zählquantoren
12:30 13:30 Mittagspause
13:30 14:15 Jonathan Höges Bisimulations-invariantes PTime und höherdimensionaler mu-Kalkül

Organisation

Die Veranstaltung wird als Blockseminar am Ende der Vorlesungszeit durchgeführt. Die Vorbesprechung findet am Donnerstag, den 19. März um 10 Uhr in Raum 4116 (Seminarraum des Lehrstuhls) statt.

Zeitplan

06.04. Gliederung
04.05. Ausarbeitung
29.05. Endgültige Fassung
15.06. Folien

Inhalt

Fixpunktkalküle spielen in der Mathematischen Logik und in vielen Bereichen der Informatik eine zentrale Rolle. Wichtige Beispiele sind:

  • Fixpunktlogiken wie LFP, IFP, PFP als Erweiterung der Prädikatenlogik, mit Anwendungen in der deskriptiven Komplexitätstheorie.
  • Der modale μ-Kalkül (und dessen Fragmente, wie etwa PDL oder die temporalen Logiken LTL, CTL, CTL*) mit wichtigen Anwendungen in der automatischen Verifikation (via Model-Checking).
  • Die Datenbank-Anfragesprache Datalog und deren Erweiterungen zur Formalisierung von Anfragen, welche Rekursion bzw. unbeschränkte Iteration erfordern und daher in einfachen Formalismen wie der relationalen Algebra oder SQL nicht ausgedrückt werden können.
  • Modale Logiken in der Wissensrepräsentation, mit Fixpunkten etwa zur Beschreibung von "common knowledge".
Im Seminar werden, ausgehend von den Grundlagen von Fixpunkt-Konstrukten, algorithmische, komplexitätstheoretische und modelltheoretische Fragen behandelt.

Themen

Thema Vortragende(r) Betreuer(in) Literatur
Der modale μ-Kalkül Malte Nuhn M. Ummels [Kir02, Zap02]
Das stetige Fragment des μ-Kalküls Julian Pott D. Fischer [Fon08]
Äquivalenz von LFP und IFP Lars Feyerabend Ł. Kaiser [Kre02a, Kre02b, GS86]
Inflationäre Fixpunkte in der Modallogik Vladislavs Serebro M. Ummels [DGK04, Kre02b]
Fixpunktlogik mit Zählquantoren Florian Weingarten R. Rabinovich [FG00]
Bisimulations-invariantes PTime und höherdimensionaler mu-Kalkül Jonathan Höges B. Puchala [Ott99, GKL+07]
Der Satz von Abiteboul und Vianu André Goliath T. Ganzow [Daw93, DLW95, Ott08]

Literatur

Zuordnung

  • Mathematik-Studiengänge: Diplom, Bachelor, Lehramt (SII), Computermathematik
  • Informatik-Studiengänge: Diplom, Bachelor, Lehramt (SII)

Voraussetzungen

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

Rückfragen

Erich Grädel, Diana Fischer, Tobias Ganzow, Łukasz Kaiser, Bernd Puchala, Roman Rabinovich, Michael Ummels