Algorithmische Modelltheorie

SS 2016

Aktuelles

  • An extended version of Chapter 3 of the lecture notes is now online (which includes the lower bound proof for the Gaifman normal form).
  • As discussed in the last lecture, exercises are moved to Wednesday, 12:15 - 13:45 (AH I).

Termine

Art Termin Ort   Veranstalter
V4 Di 10:15 – 11:45 AH II Beginn 19. April E. Grädel, W. Pakusa
Do 10:15 – 11:45 AH I Beginn 14. April E. Grädel, W. Pakusa
Ü2 Mi 12:15 – 13:45 AH I Beginn 27. April F. Reinhardt, M. Voit

Übungen

Skript

Inhalt

  • Entscheidbare und unentscheidbare Theorien
  • Endliche-Modell-Eigenschaft
  • Deskriptive Komplexität: Logische Charakterisierung von Komplexitätsklassen
  • Lokalität der Prädikatenlogik, 0-1-Gesetze
  • Logiken mit transitiver Hülle, Fixpunktlogiken

Lernziele

  • Verständnis der Zusammenhänge von logischer Definierbarkeit und algorithmischer Komplexität (Entscheidbarkeit von Theorien, Auswertungsalgorithmen, logische Charakterisierungen von Komplexitätsklassen).
  • Beherrschen der modelltheoretischen und algorithmischen Methoden zur Analyse der Ausdrucksstärke und Komplexität logischer Spezifikationen auf endlichen und endlich präsentierbaren Strukturen.
  • Fähigkeit, mit den fundamentalen Logiken der algorithmischen Modelltheorie umzugehen und diese in konkreten Szenarien anzuwenden.

Literatur

Voraussetzungen

  • Mathematische Logik

Zuordnung

  • Computermathematik (D)/Hauptstudium/Hauptfach Computermathematik
  • Informatik (D)/Hauptstudium/Theoretische Informatik
  • Informatik (D)/Anwendungsfächer/Mathematik
  • Mathematik (D)/Hauptstudium/Reine Mathematik
  • Informatik (M.A.)/Hauptstudium
  • Mathematik (M.A.)
  • Technik-Kommunikation (M.A.)/2. Hauptfach (Technisches Fach)/Grundlagen der Informatik/Hauptstudium/Spezialisierung Informatik
  • Informatik (GYM+GS,SII)/Hauptstudium/C. Mathematische Methoden der Informatik
  • Mathematik (B.Sc.)/Mathematik (WS)/5. Semester
  • Mathematik (B.Sc.)/Mathematik (SS)/6. Semester
  • Informatik (M.Sc.)/Theoretische Informatik
  • Mathematik (M.Sc.)/Mathematik/Reine Mathematik
  • Software Systems Engineering (M.Sc.)/Theoretical Foundations of Software Systems Engineering
  • Software Systems Engineering (M.Sc.)/[MPO2010] Theoretical Computer Science

Rückfragen

Erich Grädel, Wied Pakusa