Aktuelles

• 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).

Termine

Art	Termin				Ort		Veranstalter
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

Inhalt

• Entscheidbare und unentscheidbare Theorien
• Endliche-Modell-Eigenschaft
• Deskriptive Komplexität: Logische Charakterisierung von Komplexitätsklassen
• Lokalität der Prädikatenlogik, 0-1-Gesetze
• Logiken mit transitiver Hülle, Fixpunktlogiken

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.

Literatur

[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.

Voraussetzungen

• Mathematische Logik

Zuordnung

• 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

Rückfragen

Erich Grädel, Matthias Naaf