Termine

Art	Termin				Ort		Veranstalter
V4	Mi 10:00 – 11:30				AH I	Beginn 17. April	E. Grädel
	Do 10:00 – 11:30				AH I		E. Grädel
Ü2	Di 17:15 - 18:45				AH VI		D. Berwanger, A. Blumensath

Übungen

• Übung 1 [ps]
• Übung 2 [ps]
• Übung 3 [ps]
• Übung 4 [ps]
• Übung 5 [ps]
• Übung 6 [ps]
• Übung 7 [ps]
• Übung 8 [ps]
• Übung 9 [ps]
• Übung 10 [ps]

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

[1]	S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
[2]	H. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1999.
[3]	N. Immerman. Descriptive Complexity. Springer, 1999.

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