Algorithmic Model Theory
WS 2022/23
News
- 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).
Schedule
| 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 | |||
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 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. |
Prerequisites
- Mathematical Logic
Classification
- 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
Contact
Erich Grädel, Matthias Naaf