Algorithmische Modelltheorie

SS 2024

Aktuelles

  • Anmeldung: Bitte melden Sie sich zur Vorlesung über RWTHonline an. Zu den Prüfungen müssen Sie sich separat anmelden.

  • Die vollständigen Lernmaterialien sind nur im Moodle-Lernraum verfügbar.

Termine

Art Termin Ort   Veranstalter
V4 Mo 12:30 14:00 2350|111 (AH II) Vorlesung (Beginn 15. April) E. Grädel
Mi 12:30 14:00 2350|028 (AH I) Vorlesung (Beginn 10. April) E. Grädel
Ü2 Do 16:30 18:00 1010|141 (IV) und online (Link) Globalübung (Beginn 25. April) M. Naaf, S. Brinke

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

[1] S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
[2] E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Springer-Verlag, 1997.
[3] H. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1999.
[4] E. Grädel, P. G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Y. Vardi, Y. Venema, and S.Weinstein. Finite Model Theory and Its Applications. Springer-Verlag, 2007.
[5] E. Grädel and G. McColm. On the Power of Deterministic Transitive Closures. Information and Computation, vol. 119, pp. 129–135, 1995.
[6] E. Grädel. Finite Model Theory and Descriptive Complexity. In Finite Model Theory and Its Applications, pp. 125–230. , 2007.
[7] N. Immerman. Descriptive Complexity. Springer, 1999.
[8] L. Libkin. Elements of Finite Model Theory. Springer, 2004.

Voraussetzungen

  • Mathematische Logik

Zuordnung

  • Informatik (B.Sc.) / Wahlpflichtbereich Theoretische Informatik
  • Mathematik (B.Sc.) / Wahlpflichtbereich
  • Informatik (M.Sc.) / Theoretische Informatik
  • Mathematik (M.Sc.) / Reine Mathematik
  • Data Science (M.Sc.) / Computer Science
  • Software Systems Engineering (M.Sc.) / Theoretical Foundations of Software Systems Engineering

Rückfragen

Erich Grädel, Lovro Mrkonjić