Organisation

Die Vorträge finden statt am:

• Donnerstag, 10. Juli, im Seminarraum 9U09 (E3, Ahornstr. 55)

Die Vorträge können wahlweise auf deutsch oder englisch gehalten werden.

Deadlines

bis 15.4.	Vorbesprechung
30.4.	Gliederung
31.5.	Ausarbeitung
20.6.	Endgültige Fassung
1.7.	Folien
10.7.	Vorträge

Schedule

Donnerstag, 10. Juli
10:00	–	10:30	Thomas Schemmer	First-order logic and circuit complexity
10:35	–	11:05	Oliver Major	On symmetric circuits and fixed-point logics
11:25	–	11:55	Friedrich Leonard Dahlmann	Tree canonization and transitive closure
12:00	–	12:30	Gustav Leopold Grabolle	L-Recursion and a logic for logarithmic space
14:30	–	15:00	Tuan Anh Nguyen	On finite rigid structures
15:05	–	15:35	Marc Selders	Locality of order-invariant first-order formulas

Content

In diesem Seminar sollen Zusammenhänge zwischen logischer Definierbarkeit und algorithmischer Komplexität thematisiert werden. Dabei werden zentrale Methoden und Konzepte der Endlichen Modelltheorie vorgestellt, und Verbindungen zu wichtigen Fragestellungen der algorithmischen Komplexitätstheorie diskutiert.

Die Endliche Modelltheorie untersucht die Eigenschaften und das Verhalten von Logiken (wie z.B. der Prädikatenlogik) die sich ergeben, wenn als mögliche Modelle nur endliche Strukturen betrachtet werden. Klassische Fragestellungen umfassen etwa die relative Ausdrucksstärke verschiedener Logiken untereinander, oder die strukturelle und algorithmische Komplexität von definerbaren Strukturklassen sowie deren asymptotische Wahrscheinlichkeit.

In diesem Seminar wird vor allem das Teilgebiet der deskriptiven Komplexitätstheorie genauer beleuchtet. Ausgangspunkt ist die Frage nach der algorithmischen Komplexität von Entscheidungsproblemen für Logiken auf endlichen Strukturen (z.B. Modelchecking-Problem und Äquivalenz-Problem). Überraschenderweise ergeben sich hierbei starke Zusammenhänge zwischen klassischen Fragestellungen der Logik und wichtigen Problemen der algorithmischen Komplexitätstheorie. Bekannte Beispiele sind die Charakterisierung der Komplexitätsklasse NP durch die existentielle Logik zweiter Stufe, oder die logische (und spieltheoretische) Formulierung eines (für die Praxis sehr bedeutsamen) Algorithmus für das Graphisomorphieproblem.

Folgenden Aspekte werden innerhalb des Seminars genauer thematisiert:

• Wichtige Werkzeuge der endlichen Modelltheorie, z.B. Ehrenfeucht-Fraïsse Spiele und Lokalitätsbegriffe
• Die Frage nach einer Logik für Polynomialzeit
• Logiken für Logspace-Klassen
• k-Variablen Logik und das Graphisomorphieproblem
• Die Ausdrucksstärke von Fixpunktlogik mit Zählquantoren
• Lineare Algebra und logische Definierbarkeit

Für das Seminar sind Kenntnisse aus der Vorlesung Mathematische Logik notwendig; Kenntnisse aus der Vorlesung Algorithmische Modelltheorie sind wünschenswert, aber nicht notwendig.

Topics

Thema	Vortragende(r)	Betreuer(in)	Literatur
Tree canonization and transitive closure	Friedrich Leonard Dahlmann	Faried Abu Zaid	[EtIm00]
L-Recursion and a logic for logarithmic space	Gustav Leopold Grabolle	Wied Pakusa	[GrGrHeLa11]
First-order logic and circuit complexity	Thomas Schemmer	Svenja Schalthöfer	[Vo99]
On symmetric circuits and fixed-point logics	Oliver Major	Svenja Schalthöfer	[AnDa14]
On finite rigid structures	Tuan Anh Nguyen	Simon Lessenich	[GuSh96]
Order-invariant logics	Oliver Bösing	Frederic Reinhardt	[Sc13, Li04]
Locality of order-invariant first-order formulas	Marc Selders	Frederic Reinhardt	[GrSc00]

Literature

[AnDa14]	M. Anderson and A. Dawar. On Symmetric Circuits and Fixed-Point Logics. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) (E. W. Mayr and N. Portier, Eds.), vol. 25 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 41–52, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2014.
[DaGrKrSc07]	A. Dawar, M. Grohe, S. Kreutzer, and N. Schweikardt. Model Theory Makes Formulas Large. In Automata, Languages and Programming (L. Arge, C. Cachin, T. Jurdziński, and A. Tarlecki, Eds.), vol. 4596 of Lecture Notes in Computer Science, pp. 913-924. Springer Berlin Heidelberg, 2007.
[EiGr10]	K. Eickmeyer and M. Grohe. Randomisation and Derandomisation in Descriptive Complexity Theory. In Computer Science Logic (A. Dawar and H. Veith, Eds.), vol. 6247 of Lecture Notes in Computer Science, pp. 275-289. Springer Berlin Heidelberg, 2010.
[El12]	M. Elberfeld. Space and Circuit Complexity of Monadic Second-Order Definable Problems on Tree-Decomposable Structures. PhD thesis, Universität zu Lübeck, 2012.
[ElGrTa12]	M. Elberfeld, M. Grohe, and T. Tantau. Where First-Order and Monadic Second-Order Logic Coincide. In LICS, pp. 265-274. IEEE, 2012.
[EtIm00]	K. Etessami and N. Immerman. Tree Canonization and Transitive Closure. Inf. Comput., vol. 157(1-2), pp. 2-24, 2000.
[GrGrHeLa11]	M. Grohe, B. Gru\ssien, A. Hernich, and B. Laubner. L-Recursion and a new Logic for Logarithmic Space. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (M. Bezem, Ed.), vol. 12 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 277–291, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2011.
[GrSc00]	M. Grohe and T. Schwentick. Locality of Order-invariant First-order Formulas. ACM Trans. Comput. Logic, vol. 1(1), pp. 112–130, 2000.
[GuSh96]	Y. Gurevich and S. Shelah. On Finite Rigid Structures. The Journal of Symbolic Logic, vol. 61(2), pp. pp. 549-562, 1996.
[Li04]	L. Libkin. Elements of Finite Model Theory. Springer, 2004.
[Sc13]	N. Schweikardt. A short tutorial on order-invariant first-order logic. In Proc.\ 8th International Computer Science Symposium in Russia (CSR'13), 2013.
[Vo99]	H. Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1999.

Classification

• Informatik (B.Sc.)/Seminar Informatik
• Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
• Informatik (M.Sc.)/Seminar Theoretische Informatik
• Mathematik (M.Sc.)/Seminar: Logik, Komplexität, Spiele (Reine Mathematik)
• Informatik (D)/Hauptstudium/Theoretische Informatik
• Mathematik (D)/Hauptstudium/Reine Mathematik
• Informatik (S II)
• Mathematik (S II)/Hauptstudium/Modul Algebra
• Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Prerequisites

• Module Mathematical Logic
• for B.Sc. Computer Science: Module "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Contact

Erich Grädel, Simon Lessenich, Faried Abu Zaid, Wied Pakusa, Frederic Reinhardt