Algorithmic Model Theory

SS 2008

News

  • On Wednesday, 11 June, the lecture as well as the exercise class are cancelled due to the "Studieninformationstag" (Dies).
  • The exercise class on Wednesday, 28 May, is cancelled due to the RWTH Sports Day. Hence, the current exercises are due 3 June.

Schedule

Type Date Location   Organizer
V4 Di 10:00 – 11:30 AH I   E. Grädel, D. Berwanger
Mi 10:00 – 11:30 AH I Beginn 9. April E. Grädel, D. Berwanger
Ü2 Mi 17:15 – 18:45 5056 Beginn 16. April T. Ganzow

Coursework

Supplements

  • Slide: Interpretation of Q in Z [pdf]

Content

  • Decidable and undecidable theories, interpretations
  • Logic and automata,
  • Monadic theories,
  • First-order logic on finite structures, locality, Ehrenfeucht-Fraisse games,
  • TC-logics, fixed-point logics,
  • Logical characterisation of complexity classes,
  • Finitely presentable structures, automatic structures.

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.

Literature

Prerequisites

  • Mathematische Logik

Classification

  • Informatiker: Theoretische Informatik, Vertiefungsfach, Anwendungsfach Mathematik
  • Mathematiker (D): Reine Mathematik
  • Mathematiker (B.Sc.)
  • Lehramtskandidaten Informatik: Mathematische Methoden der Informatik (C)
  • Software Systems Engineering (M.Sc.): Theoretical Computer Science
  • Sonstige: Informatik

Assessment

  • 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

Contact

Erich Grädel, Dietmar Berwanger, Tobias Ganzow