Finite Model Theory
SS 2002
Schedule
| Type | Date | Location | Organizer | ||||
|---|---|---|---|---|---|---|---|
| V4 | Mi 10:00 – 11:30 | AH I | Beginn 17. April | E. Grädel | |||
| Do 10:00 – 11:30 | AH I | E. Grädel | |||||
| Ü2 | Di 17:15 - 18:45 | AH VI | D. Berwanger, A. Blumensath | ||||
Coursework
- Homework 1 [ps]
- Homework 2 [ps]
- Homework 3 [ps]
- Homework 4 [ps]
- Homework 5 [ps]
- Homework 6 [ps]
- Homework 7 [ps]
- Homework 8 [ps]
- Homework 9 [ps]
- Homework 10 [ps]
Supplements
- Übersicht zu Ehrenfeucht-Fraïssé-Spielen [ps]
- Alternierende Komplexitätsklassen [ps]
- Das Auswertungsproblem für die Prädikatenlogik [ps]
Content
Introduction to finite model theory and descriptive complexity:- Relationship between logical definability and algorithmic complexity (evaluation algorithms, logics capturing complexity classes).
- Fixed point logics.
- Logic and games (model checking via evaluation games, analysis of expressive power via model comparison games).
- Applications: databases, verification.
- Extensions to infinite structures (computational model theory).
Literature
| [1] | S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995. |
| [2] | H. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1999. |
| [3] | N. Immerman. Descriptive Complexity. Springer, 1999. |
Prerequisites
- Mathematische Logik
Classification
- Informatiker: Theoretische Informatik, Vertiefungsfach
- Mathematiker: Reine Mathematik, Angewandte Mathematik
- Lehramtskandidaten: Algebra und Grundlagen der Mathematik (B), Angewandte Mathematik (D)
- Sonstige: Informatik