Algorithmic Model Theory

SS 2016

News

  • 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).

Schedule

Type Date Location   Organizer
V4 Tue 10:15 – 11:45 AH II Start: April, 19 E. Grädel, W. Pakusa
Thu 10:15 – 11:45 AH I Start: April, 14 E. Grädel, W. Pakusa
Ü2 Wed 12:15 – 13:45 AH I Start: April, 27 W. Pakusa, M. Voit, F. Reinhardt

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

Learning Objectives

  • Understanding the relation between logical definability and algorithmic complexity (decidability of theories, evaluation algorithms, logical characterisations of complexity classes).
  • Learning the methods from model theory and algorithmic complexity theory to analyse the expressive power and complexity of logical specifications on finite or finitely representable structures.
  • Learning to work with fundamental logics of algorithmic model theory and in their application in concrete scenarios.

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

  • Mathematical Logic

Classification

  • 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

Contact

Erich Grädel, Wied Pakusa