Algorithmic Model Theory
SS 2008
News
The lecture on Tuesday, 6 May, is cancelled due to the "Fachschaftsvollversammlung".Schedule
| Art | Termin | Ort | Veranstalter | |
|---|---|---|---|---|
| V4 | Di 10:00 – 11:30 | AH I | E. Grädel, D. Berwanger | |
| Mi 10:00 – 11:30 | AH I | Beginn 9. April | E. Grädel, D. Berwanger | |
| Ü2 | Mi 17:15 – 18:45 | 5056 | Beginn 16. April | E. Grädel, D. Berwanger |
Coursework
Content
- Decidable and undecidable theories, interpretations
- Logic and automata,
- Monadic theories,
- First-order logic on finite structures, locality, Ehrenfeucht-Fraisse games,
- TC-logics, fixed-point logics,
- Logical characterisation of complexity classes,
- Finitely presentable structures, automatic structures.
Lernziele
- Verständnis der Zusammenhänge von logischer Definierbarkeit und algorithmischer Komplexität (Entscheidbarkeit von Theorien, Auswertungsalgorithmen, logische Charakterisierungen von Komplexitätsklassen).
- Beherrschen der modelltheoretischen und algorithmischen Methoden zur Analyse der Ausdrucksstärke und Komplexität logischer Spezifikationen auf endlichen und endlich präsentierbaren Strukturen.
- Fähigkeit, mit den fundamentalen Logiken der algorithmischen Modelltheorie umzugehen und diese in konkreten Szenarien anzuwenden.
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
- Mathematische Logik
Classification
- Informatiker: Theoretische Informatik, Vertiefungsfach, Anwendungsfach Mathematik
- Mathematiker (D): Reine Mathematik
- Mathematiker (B.Sc.)
- Lehramtskandidaten Informatik: Mathematische Methoden der Informatik (C)
- Software Systems Engineering (M.Sc.): Theoretical Computer Science
- Sonstige: Informatik
Assessment
- Bachelor- und Masterstudiengänge: Lösen von 50% der Übungsaufgaben und Bestehen einer mündlichen Prüfung im Umfang von 30 Minuten
- Diplomstudiengänge: Übungsschein bei Lösen von 50% der Übungsaufgaben und aktiver Teilnahme an den Übungen
Contact
Erich Grädel, Dietmar Berwanger, Tobias Ganzow