Algorithmic Model Theory

SS 2010

News

  • Das letzte Kapitel des Skripts ist jetzt online.
  • Am Dienstag, dem 13.07., findet die Vorlesung nicht statt.
  • Am Mittwoch, dem 09.06., findet die Vorlesung wegen des Studieninformationstags (Dies) nicht statt.

Schedule

Type Date Location   Organizer
V4 Tue 10:00 – 11:30 AH I Start: April, 20 E. Grädel, Ł. Kaiser
Wed 10:00 – 11:30 AH I Start: April, 14 E. Grädel, Ł. Kaiser
Ü2 Wed 17:15 – 18:45 5056 Start: April, 28 R. Rabinovich

Coursework

Lecture Notes

Content

  • Decidable and undecidable theories
  • Finite model property
  • Descriptive complexity: logical characterisation of complexity classes
  • Locality of first order logic, 0-1 laws
  • Logics with transitive closure, fixed-point logics

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.

Literature

[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. Finite Model Theory and Descriptive Complexity. In Finite Model Theory and Its Applications, pp. 125–230. Springer-Verlag, 2007.
[6] N. Immerman. Descriptive Complexity. Springer, 1999.
[7] L. Libkin. Elements of Finite Model Theory. Springer, 2004.

Prerequisites

  • Mathematische Logik

Classification

  • Mathematik (D): Reine Mathematik
  • Mathematik (B.Sc.): 5./6. Semester
  • Informatik (D): Theoretische Informatik, Vertiefungsfach, Anwendungsfach Mathematik
  • Informatik (M.Sc.): Theoretische Informatik
  • Lehramtskandidaten Informatik: Mathematische Methoden der Informatik (C)
  • Software Systems Engineering (M.Sc.): Theoretical Computer Science

Assessment

  • Bachelor- und Masterstudiengänge: Lösen von 50% der Übungsaufgaben und Bestehen einer mündlichen Prüfung im Umfang von 30 Minuten
  • Diplomstudiengänge: Übungsschein bei Lösen von 50% der Übungsaufgaben und aktiver Teilnahme an den Übungen

Contact

Erich Grädel, Łukasz Kaiser, Roman Rabinovich