Algorithmische Modelltheorie

WS 2019/20

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 lectures on the topics of transitive closures and meta-finite model theory are not relevant for the exam. There are no lecture notes on these topics, but you can read up on them in the entries [5] and [6] (section 3.6) of the literature given below.
  • Please send an e-mail to Prof. Grädel by the 31st of January with two suggested dates for your oral exam. The dates should be before the 31st of March.
  • The registration in RWTHonline is now possible. If you wish to take the exam, please register by Tuesday, 21st of January. After everyone has had a chance to register themselves, I will check in with anyone who registered per E-mail but not in RWTHonline and register them by hand if possible.
  • 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

Skript

  • Kapitel 1: The Classical Decision Problem for FO [pdf] [pdf-2up]
  • Kapitel 2: Descriptive Complexity [pdf]
  • Kapitel 3: LFP and Infinitary Logics [pdf]
  • Kapitel 4: Expressive Power of First-Order Logic [pdf]
  • Kapitel 5: Zero-one laws [pdf]
  • Kapitel 6: Modal, Inflationary and Partial Fixed Points [pdf]
  • Kapitel 7: Fixed-point Logic with Counting [pdf] [pdf]

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

  • 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