Algorithmische Modelltheorie 2

SS 2014

Aktuelles

  • (11.07., 16:12 Uhr) Am Montag, dem 14.7., findet keine Vorlesung statt. Die Übungsgruppe um 15:00 Uhr findet jedoch statt. Das letzte Übungsblatt (Übung 11) wird erst am Montag online gestellt und kann dann bis zum 21.7. bearbeitet werden. In der Übungsgruppe wird dafür näher auf Dependence und Independence Logic eingegangen und exemplarisch einige Aufgaben hierzu vorgerechnet. Die Musterlösung zu Übung 11 wird dann am 21.7. online gestellt.
  • (29.05., 12:35 Uhr) Auf Übungsblatt 6, Aufgabe 1 b) wurde ein Tippfehler korrigiert (S_a yz statt S_a zy).
  • (14.05., 17:48 Uhr) Auf Übungsblatt 4, Aufgabe 2 c) und im Hinweis zu Aufgabe 2 d) wurde ein Fehler korrigiert.
  • Sofern es keine Einwände gibt wird der wöchentliche Übungstermin auf montags verlegt.
  • Die erste Übung findet am 28.4. im Anschluss an die Vorlesung im Seminarraum Informatik 7 (Raum 4116, 1. Etage E1) statt.
  • Die Übungen können in Gruppen bearbeitet werden (max. 3 Studenten) und sind spätestens montags um 15 Uhr im Kasten am Lehrstuhl (bzw. in der Vorlesung oder Übung) abzugeben. Neue Aufgabenblätter werden in der Regel montags auf der Homepage verfügbar sein.

Termine

Art Termin Ort   Veranstalter
V2 Mo 13:15 – 14:45 AH II Beginn 14. April E. Grädel
Ü2 Mo 15:00 – 16:30 4116 Beginn 28. April F. Reinhardt

Übungen

Materialien

  • Folien - Logics for dependence and independence [pdf]

Inhalt

  • Logische Charakterisierung von Komplexitätsklassen
  • Endlich präsentierbare Strukturen
  • Automatische Strukturen
  • Modellvergleichsspiele
  • Lokalität
  • Fixpunktlogiken
  • Logiken mit Teamsemantik
  • Aktuelle Forschungsresultate und Fragestellungen der Algorithmischen Modelltheorie

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.
[8] J. A. Väänänen. Dependence Logic - A New Approach to Independence Friendly Logic. Cambridge University Press, 2007.

Voraussetzungen

  • Mathematische Logik
  • Algorithmische Modelltheorie 1

Zuordnung

  • Informatik (B.Sc./M.Sc.): Wahlpflichtmodul Theoretische Informatik, Anwendungsfach Mathematik
  • Mathematik (B.Sc.): 4.,5.,6. Semester
  • Mathematik (M.Sc.): Reine Mathematik

Leistungsnachweis

  • 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

Rückfragen

Erich Grädel, Frederic Reinhardt