Aktuelles

• Die Vorlesung wird von der Video AG aufgezeichnet. Die Videos werden unter https://rwth.video/24ss-algomod zur Verfügung gestellt.

• Anmeldung: Bitte melden Sie sich zur Vorlesung über RWTHonline an. Zu den Prüfungen müssen Sie sich separat anmelden.

• Die vollständigen Lernmaterialien sind nur im Moodle-Lernraum verfügbar.

Termine

Art	Termin				Ort		Veranstalter
V4	Mo	12:30	–	14:00	2350|111 (AH II)	Vorlesung (Beginn 15. April)	E. Grädel
	Mi	12:30	–	14:00	2350|028 (AH I)	Vorlesung (Beginn 10. April)	E. Grädel
Ü2	Do	16:30	–	18:00	1010|141 (IV) und online (Link)	Globalübung (Beginn 25. April)	S. Brinke, J. Arpasi, 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 (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

Rückfragen

Erich Grädel, Lovro Mrkonjić