Seminar Logik, Komplexität, Spiele: Endliche Modelltheorie

WS 2012/13

Aktuelles

Die Vorträge finden statt am:

  • Dienstag, 29. Januar, im Seminarraum des Lehrstuhls i2 (Raum 4201b, E1, Ahornstr. 55)
  • Mittwoch, 30. Januar, in unserem Seminarraum (Raum 4116, E1, Ahornstr. 55)
Die Vorträge können wahlweise auf deutsch oder englisch gehalten werden.

Organisation

Die Veranstaltung wird als Blockseminar angeboten.

Zeitplan

22.10.Gliederung, Konzeption
19.11.Ausarbeitung
10.12.Endgültige Fassung
14.01.Folien
29.01., 30.01.Vorträge

Programm

Dienstag, 29. Januar
09:0009:45Norman MüllerLokalität der Prädikatenlogik: Die Sätze von Hanf und Gaifman
09:4510:30Martin RitzertZusammenhänge und Charakterisierungen verschiedener Lokalitätskonzepte
10:4511:30Evgeny SaleevEine logische Charakterisierung von Lokalität
11:3012:15Felix CanavoiMonadisches NP vs. monadisches co-NP
13:3014:15Daniel NeuenErweiterungen von monadischem NP
14:1515:00Martin BellgardtEndliche Modelltheorie erzeugt lange Formeln
Mittwoch, 30. Januar
08:3009:15Marlene GregorekKlassische Werkzeuge der Modelltheorie angewandt im Endlichen
09:1510:00Patrick LandwehrÄquivalenz in der k-Variablen Logik ist vollständig für PTIME
10:1511:00Waldemar LaubeAlgorithmische Komplexität von Ehrenfeucht-Fraïsse Spielen
11:0011:45Svenja SchalthöferUnterscheidbarkeit von Strukturen in existentieller k-Variablen Logik
13:3014:15Wadim PessinLineare Gleichungssysteme und Äquivalenz in der k-Variablen Logik
14:1515:00Stefan BleßLokalität von ordnungs-invarianter Prädikatenlogik
15:1516:00Matthias KlupschAusdrucksstärke von Prädikatenlogik mit invarianten Operatoren

Inhalt

In diesem Seminar sollen grundlegende Konzepte und Methoden der Endlichen Modelltheorie und einige ihrer Anwendungen vorgestellt werden.

Die Endliche Modelltheorie untersucht die Eigenschaften und das Verhalten von Logiken (wie z.B. der Prädikatenlogik) die sich ergeben, wenn als mögliche Modelle nur endliche Strukturen betrachtet werden. Klassische Fragestellungen umfassen etwa die relative Ausdrucksstärke verschiedener Logiken untereinander, oder die strukturelle und algorithmische Komplexität von definerbaren Strukturklassen sowie deren asymptotische Wahrscheinlichkeit. Hierbei sind Zusammenhänge zwischen logischer Definierbarkeit und algorithmischer Komplexität von Klassen endlicher Strukturen von besonderem Interesse.

Es stellt sich heraus, dass viele Werkzeuge der klassischen Modelltheorie, wie etwa der Kompaktheitssatz oder der Vollständigkeitssatz für die Prädikatenlogik, auf der Klasse der endlichen Strukturen nicht zur Verfügung stehen. Allerdings bleibt die Charakterisierung der Ausdrucksstärke von FO durch Ehrenfeucht-Fraïsse Spiele auch im Endlichen erhalten.

Aus diesem Grund nehmen in der Endlichen Modelltheorie kombinatorische und spieltheoretische Argumente eine zentrale Rolle ein. So kann mit Hilfe von Ehrenfeucht-Fraïsse Spielen etwa gezeigt werden, dass alle in FO definierbaren Relationen (in einem präzisen Sinne) lokal sind (z.B. Erreichbarkeit in Graphen kann nicht ausgedrückt werden), oder dass ein Satz der Prädikatenlogik entweder in fast allen oder fast keiner endlichen Struktur gilt.

Folgenden Aspekte werden innerhalb des Seminars genauer thematisiert:

  • Ehrenfeucht-Fraïsse Spiele;
  • Lokalitätsbegriffe für (Erweiterungen von) FO;
  • Model-Checking Probleme für FO;
  • k-Variablen Fragmente von FO;
  • Logische Operatoren für Erreichbarkeit;
  • 0-1 Gesetze.

Für das Seminar sind Kenntnisse aus der Vorlesung Mathematische Logik notwendig; Kenntnisse aus der Vorlesung Algorithmische Modelltheorie sind wünschenswert, aber nicht notwendig.

Themen

ThemaVortragende(r)Betreuer(in)Literatur
Lokalität der Prädikatenlogik: Die Sätze von Hanf und GaifmanNorman MüllerSimon Lessenich[Li04, EbFl95]
Zusammenhänge und Charakterisierungen verschiedener LokalitätskonzepteMartin RitzertSimon Lessenich[HeLiNu99, Li04]
Eine logische Charakterisierung von LokalitätEvgeny SaleevFaried Abu Zaid[Li01]
Monadisches NP vs. monadisches co-NPFelix CanavoiWied Pakusa[FaStVa95]
Erweiterungen von monadischem NPDaniel NeuenWied Pakusa[AjFaSt00, JaMa01]
Endliche Modelltheorie erzeugt lange FormelnMartin BellgardtFaried Abu Zaid[DaGrKrSc07]
Klassische Werkzeuge der Modelltheorie angewandt im EndlichenMarlene GregorekRoman Rabinovich[LiWe12]
Äquivalenz in der k-Variablen Logik ist vollständig für PTIMEPatrick LandwehrBernd Puchala[Gr99]
Algorithmische Komplexität von Ehrenfeucht-Fraïsse SpielenWaldemar LaubeBernd Puchala[Pe98]
Unterscheidbarkeit von Strukturen in existentieller k-Variablen LogikSvenja SchalthöferBernd Puchala[KoPa03, Be12]
Lineare Gleichungssysteme und Äquivalenz in der k-Variablen LogikWadim PessinWied Pakusa[GrOt12]
Lokalität von ordnungs-invarianter PrädikatenlogikStefan BleßDiana Fischer[GrSc00]
Ausdrucksstärke von Prädikatenlogik mit invarianten OperatorenMatthias KlupschDiana Fischer[Ot00, Ro07]

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 (D)/Hauptstudium/Theoretische Informatik
  • Mathematik (D)/Hauptstudium/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, Faried Abu Zaid, Diana Fischer, Simon Lessenich, Wied Pakusa, Bernd Puchala, Roman Rabinovich