Endliche Modelltheorie

SS 2002

Termine

ArtTerminOrt Veranstalter
V4Mi 10:00 – 11:30AH IBeginn 17. AprilE. Grädel
Do 10:00 – 11:30AH I E. Grädel
Ü2Di 17:15 - 18:45AH VI D. Berwanger, A. Blumensath

Übungen

Materialien

  • Übersicht zu Ehrenfeucht-Fraïssé-Spielen [ps]
  • Alternierende Komplexitätsklassen [ps]
  • Das Auswertungsproblem für die Prädikatenlogik [ps]

Inhalt

Einführung in die Modelltheorie endlicher Strukturen und die Deskriptive Komplexitätstheorie.
  • Der Zusammenhang von logischer Definierbarkeit und algorithmischer Komplexität (z.B. Auswertungsalgorithmen, logische Charakterisierungen von Komplexitätsklassen).
  • Fixpunktlogiken.
  • Logik und Spiele (Model Checking via Auswertungsspiele, Analyse der Ausdrucksstärke mit Modellvergleichsspielen).
  • Anwendungsbereiche: Datenbanken, Verifikation
  • Erweiterungen auf unendliche Strukturen (computational model theory).

Literatur

Voraussetzungen

  • Mathematische Logik

Zuordnung

  • Informatiker: Theoretische Informatik, Vertiefungsfach
  • Mathematiker: Reine Mathematik, Angewandte Mathematik
  • Lehramtskandidaten: Algebra und Grundlagen der Mathematik (B), Angewandte Mathematik (D)
  • Sonstige: Informatik