Algorithmic Model Theory
SS 2024
Information
-
This year's lectures are recorded by the Video AG. Videos are available at https://rwth.video/24ss-algomod.
-
Registration: Please register to the lecture via RWTHonline. The exams require separate registrations.
-
The complete course materials are only available on our Moodle course page.
Schedule
| Type | Date | Location | Organizer | ||||
|---|---|---|---|---|---|---|---|
| V4 | Mon | 12:30 | – | 14:00 | 2350|111 (AH II) | Lecture (Start 15th April) | E. Grädel |
| Wed | 12:30 | – | 14:00 | 2350|028 (AH I) | Lecture (Start 10th April) | E. Grädel | |
| Ü2 | Thu | 16:30 | – | 18:00 | 1010|141 (IV) and online (link) | Exercise Class (Start 25th April) | S. Brinke, J. Arpasi |
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 (B.Sc.) / Wahlpflichtbereich Theoretische Informatik
- Mathematik (B.Sc.) / Wahlpflichtbereich
- Informatik (M.Sc.) / Theoretische Informatik
- Mathematik (M.Sc.) / Reine Mathematik
- Data Science (M.Sc.) / Computer Science
- Software Systems Engineering (M.Sc.) / Theoretical Foundations of Software Systems Engineering
Contact
Erich Grädel, Lovro Mrkonjić