Seminar Logik, Komplexität, Spiele: Definierbarkeit und Komplexität
SS 2014
Organisation
Die Vorträge finden statt am:
- Donnerstag, 10. Juli, im Seminarraum 9U09 (E3, Ahornstr. 55)
Zeitplan
| bis 15.4. | Vorbesprechung |
| 30.4. | Gliederung |
| 31.5. | Ausarbeitung |
| 20.6. | Endgültige Fassung |
| 1.7. | Folien |
| 10.7. | Vorträge |
Programm
| 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 |
Inhalt
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.
Themen
| 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] |
Literatur
| [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. |
Zuordnung
- 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
Voraussetzungen
- Modul Mathematische Logik
- für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"
Rückfragen
Erich Grädel, Simon Lessenich, Faried Abu Zaid, Wied Pakusa, Frederic Reinhardt