|
Logik in der Informatik
Prof. Dr. Nicole Schweikardt |
|
Aktuelles Einführung Ort und Zeit Vorträge Vortragsthemen Spielregeln
Anhand von Originalarbeiten und ergänzender Literatur werden im Seminar aktuelle Themen im Bereich Logik und Komplexität erarbeitet.
Ziele sind das Kennenlernen neuer Forschungsergebnisse, das Verstehen wissenschaftlicher Originaltexte, die Fähigkeit zur Einordnung der Inhalte und Beweistechniken, sowie deren Wiedergabe in eigener Darstellung in einem begrenzten Zeitrahmen.
Das Seminar richtet sich an fortgeschrittene Studierende in einem Diplom- oder Masterstudiengang, die sich im Bereich Logik und Komplexität spezialisieren wollen. Die Teilnahme am Seminar setzt Kenntnisse, die in der Vorlesung "Logik und Komplexität" vermittelt werden, voraus.
| 28.10. | Christoph Berkholz |
Die Frage nach einer Logik für PTIME. Basierend auf Gurevich "Logik and the Challenge of Computer Science" (1988) und Nash, Remmel, Vianu "PTIME Queries Revisited" (2005) |
| 04.11. | Nicole Schweikardt |
IFP+C: Fixpunktlogik mit Zähloperatoren. Basierend auf "Abschnitt 2.4.3" von "Chapter 2: Background from Graph Theory and Logic" des Buchs Descriptive Complexity, Canonisation, and Definable Graph Structure Theory von Martin Grohe (Version: Nov 25, 2013) und auf der "Introduction" des Artikels Fixed-point definability and polynomial time on graphs with excluded minors von Martin Grohe (J. ACM 59(5):27 (2012)) |
| 11.11. | Berit Grußien | Transduktionen |
| 18.11. | Christoph Berkholz | Untere Schranken an den Quantorenrang von k-Variablen Logik. Basierend auf einer noch unveröffentlichten Arbeit von C. Berkholz und J. Nordström. |
| 25.11. 17:00 | Lucas Heimberg | Lokalität Teil I |
| 02.12. 17:00 | Lucas Heimberg | Lokalität Teil II |
| 09.12. | Jens Keppeler | Strombasierte Aufzählung von Anfrageergebnissen für Datenbanken von geringem Grad |
| 16.12. | kein Seminar | |
| 06.01. 17:00 | Lucas Heimberg | Lokalität Teil III: Eine untere Schranke für Hanf-Normalform. |
| 13.01. | Benjamin Hauskeller | "An optimal lower bound on the number of variables for graph identifications" von J. Cai, M. Fürer und N. Immerman |
| 20.01. | kein Seminar | |
| 27.01. | Denis Erfurt | "Choiceless Computation and Symmetry" von B. Rossman |
| 03.02. | kein Seminar | |
| 10.02. | Pascal Kunz | "Choiceless Polynomial Time, Counting and Cai-Fürer-Immerman graphs" von A. Dawar, D. Richerby und B. Rossman |
An optimal construction of Hanf sentences von Benedikt Bollig
und Dietrich Kuske.
J. Applied Logic 10(2): 179-186 (2012)
Zusätzliches Material: Appendix A der Arbeit
An optimal Gaifman normal form construction for structures of
bounded degree von Lucas Heimberg, Dietrich Kuske und Nicole Schweikardt
(ausführliche Version einer bei LICS 2013 erschienenen Arbeit).
Shrinking Games and Local Formulas von H. Jerome Keisler und Wafik Boulos Lotfallah. Ann. Pure Appl. Logic 128(1-3): 215-225 (2004)
An existential locality theorem von Martin Grohe und Stefan Wöhrle. Ann. Pure Appl. Logic 129(1-3): 131-148 (2004)
An optimal lower bound on the number of variables for graph identifications von Jin-yi Cai, Martin Fürer und Neil Immerman. Combinatorica 12(4): 389-410 (1992)
Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations von Martin Fürer. ICALP 2001: 322-333
Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs von Anuj Dawar, David Richerby und Benjamin Rossman. Ann. Pure Appl. Logic 152(1-3): 31-50 (2008)
Choiceless Polynomial Time on Structures with Small Abelian Colour Classes von Faried Abu Zaid, Erich Grädel, Martin Grohe und Wied Pakusa. MFCS (1) 2014: 50-62 (als zusätzliches Material steht im Seminar eine noch unveröffentlichte Version mit ausführlichen Beweisen zur Verfügung)