Algorithmic Model Theory 2

SS 2014

Schedule

Type Date Location   Organizer
V2 Mon 13:15 – 14:45 AH II Start: April, 14 E. Grädel
Ü2 Mon 15:00 – 16:30 4116 Start: April, 28 F. Reinhardt

Coursework

Content

  • Logical characterisation of complexity classes
  • Finitely presentable structures
  • Automatic Structures
  • Model comparison games
  • Locality
  • Fixed-point logics
  • Logics with team semantics
  • Recent research results and questions in algorithmic model theory

Learning Objectives

  • Understanding the relationship between logical definability and algorithmic complexity (decidability of theories, evaluation algorithms, logical characterisations of complexity classes).
  • Mastering methods from model theory and algorithmic complexity theory to analyse the expressive power and complexity of logical specifications on finite or finitely representable structures.
  • Ability to handle the fundamental logics of algorithmic model theory and to apply them in concrete situations

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.
[8] J. A. Väänänen. Dependence Logic - A New Approach to Independence Friendly Logic. Cambridge University Press, 2007.

Prerequisites

  • Mathematical Logic
  • Algorithmic Model Theory 1

Classification

  • Informatik (B.Sc./M.Sc.): Wahlpflichtmodul Theoretische Informatik, Anwendungsfach Mathematik
  • Mathematik (B.Sc.): 4.,5.,6. Semester
  • Mathematik (M.Sc.): Reine Mathematik

Assessment

  • Bachelor- und Masterstudiengänge: solving 50% of the exercises and passing the oral exam (30 min)
  • Diplomstudiengänge: exercise certificate upon solving 50% of the exercises and active participation at the exercises

Contact

Erich Grädel, Frederic Reinhardt