Algorithmic Model Theory
WS 2019/20
Schedule
Type | Date | Location | Organizer | ||||
---|---|---|---|---|---|---|---|
V4 | Mo 10:30 – 12:00 | AH III | Start 7th October | E. Grädel | |||
Tue 08:30 – 10:00 | AH I | Start 8th October | E. Grädel | ||||
Ü2 | Tue 10:30 – 12:00 | AH III | Start 15th October |
News
- There will be no lecture next Monday, 20th January.
- The registration in RWTHonline is now possible. If you wish to take the exam, please register by Tuesday, 21st of January. After everyone has had a chance to register themselves, I will check in with anyone who registered per E-mail but not in RWTHonline and register them by hand if possible.
- The exercise sheets are published every Tuesday and are due the following Tuesday at 10:30 am. They may be handed in during the lecture or at the beginning of the exercise class. Alternatively they can be put in the box at the institute.
- You may work on the exercise sheets in groups of up to three students.
- There will be no e-learning room for this course. All necessary information can be found on this website.
- The distribution of points for exercise sheet 1 has been adjusted slightly.
Coursework
- Homework 1 [pdf]
- Homework 2 [pdf]
- Homework 3 [pdf]
- Homework 4 [pdf]
- Homework 5 [pdf]
- Homework 6 [pdf]
- Homework 7 [pdf]
- Homework 8 [pdf]
- Homework 9 [pdf]
- Homework 10 [pdf]
- Homework 11 [pdf]
- Homework 12 [pdf]
Lecture Notes
- Chapter 1: The Classical Decision Problem for FO [pdf] [pdf-2up]
- Chapter 2: Descriptive Complexity [pdf]
- Chapter 3: LFP and Infinitary Logics [pdf]
- Chapter 4: Expressive Power of First-Order Logic [pdf]
- Chapter 5: Zero-one laws [pdf]
- Chapter 6: Modal, Inflationary and Partial Fixed Points [pdf]
- Chapter 7: Fixed-point Logic with Counting [pdf] [pdf]
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
- 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