Termine

Art	Termin				Ort		Veranstalter
V4	Mo 10:30 – 12:00				AH III	Beginn 14. Oktober	E. Grädel
	Di 08:30 – 10:00				AH I	Beginn 08. Oktober	E. Grädel
Ü2	Di 10:30 – 12:00				AH III	Beginn 22. Oktober

Aktuelles

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

Übungen

• Übung 1 [pdf]
• Übung 2 [pdf]

Skript

• Kapitel 1: The Classical Decision Problem for FO [pdf] [pdf-2up]

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

Voraussetzungen

• Mathematische Logik

Zuordnung

• 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

Rückfragen

Erich Grädel