Algorithmic Model Theory

WS 2022/23


  • Please register in RWTHonline to access the Moodle course room.
  • All further information and materials are available only in the Moodle course room.
  • There will be no lecture/exercise in the first week of the semester (October 10 - October 14).


Type Date Location   Organizer
V4 Mon 10:30 – 12:00 1010|141 (IV) Begin: October 24 E. Grädel
Wed 12:30 – 14:00 2350|028 (AH I) Begin: October 19 E. Grädel
Ü2 Thu 12:30 – 14:00 1810|012 (SG 12) Begin: November 3 M. Naaf


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


[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.


  • Mathematical Logic


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


Erich Grädel, Matthias Naaf