Logik in der Informatik
Prof. Dr. Martin Grohe

Logbuch zur Vorlesung Die Komplexität des constraint satisfaction Problems

Di, 14. 4. 2009: Organisatorisches; Skript Seiten 1-9 (Kapitel 1): Die Probleme CSP, Hom, CQ und CQ Containment.
Do, 16. 4. 2009: Skript Seiten 9-14 (Kapitel 1 und 2): Einschränkungen; Der Satz von Schaefer: 0/1-gültige und horne Fälle, Polymorphismen.
Di, 21. 4. 2009: Skript Seiten 14-18 (Kapitel 2): Restliche positive Schaefer-Fälle.
Do, 23. 4. 2009: Skript Seiten 18-21 (Kapitel 2): pp-Definitionen, Muster.
Di, 28. 4. 2009: Skript Seiten 21-26 (Kapitel 2): Rest des Beweises des Satzes von Schaefer.
Do, 30. 4. 2009: Skript Seiten 26-31 (Kapitel 2 und 3): Satz von Bulatov; l,k-Konsistenz, Spielcharakterisierung, Datalog.
Di, 5. 5. 2009: Skript Seiten 31-33 (Kapitel 3): Datalog-Anfrage für l,k-Konsistenz, Weite von Datalog-Programmen, Konsistenzinvarianz von Datalog.
Do, 7. 5. 2009: Skript Seiten 33-35 (Kapitel 3): Konsistenz als Ausdrückbarkeitsgrenze für Datalog; Baumweite, Abwicklungen.
Do, 14. 5. 2009: Skript Seiten 35-38 (Kapitel 3): Abwicklungen als Mittler zwischen Baumweite und Konsistenz; Kerne.
Di, 19. 5. 2009: Skript Seiten 38-40 (Kapitel 3): Klassifikation linksseitiger Einschränkungen; Kompaktheit, Dualität.
Di, 26. 5. 2009: Skript Seiten 40-42 (Kapitel 3): Projektive k-Konsistenz.
Do, 28. 5. 2009: Skript Seiten 42-44 (Kapitel 3): Fast-Einstimmigkeitsentscheide und projektive Konsistenz; Arc-Konsistenz: Definition, Eigenschaften, Algorithmus.
Di, 2. 6. 2009: Skript Seiten 44-46 (Kapitel 3): Charakterisierung von arc-Konsitenz durch die Potenzstruktur, Folgerungen.
Do, 4. 6. 2009: Skript Seiten 46-48 (Kapitel 3): Vergleich arc-Konsistenz mit 1,k-Konsistenz Anfang.
Di, 9. 6. 2009: Skript Seiten 48-51 (Kapitel 3 und 4): Vergleich arc-Konsistenz mit 1,k-Konsistenz Ende; Algebren, Galois-Verbindung.
Do, 11. 6. 2009: Skript Seiten 51-53 (Kapitel 4): Abgeschlossenheit, Vergleich mit pp-Definitionen.
Di, 16. 6. 2009: Skript Seiten 53-54 (Kapitel 4): Vergleich Abgeschlossenheit (von Algebren) mit Termdefinitionen; Starrheit und Idempotenz.
Do, 18. 6. 2009: Skript Seiten 54-58 (Kapitel 4 und 5): Schwache fast-Einstimmigkeitsentscheide; Mal'tsev-Operationen, kompakte Darstellungen.
Do, 25. 6. 2009: Skript Seiten 58-61 (Kapitel 5): Der Algorithmus für Mal'tsev-Polymorphismen.
Di, 30. 6. 2009: Skript Seiten 63-65 (Kapitel 6): Satz von Ladner für linksseitige Einschränkungen; parametrische Dichotomie für linksseitige Einschränkungen. Ende der Vorlesung.

Mark Weyer