Logbuch

Hier finden Sie Informationen zum Verlauf der Vorlesung

  1. Montag, 13.10.08
    Kapitel 1: Übersicht über die Vorlesung, Organisatorisches
  2. Dienstag, 14.10.08
    Kapitel 2 (bis Folie 28): Wiederholung (Mathematische Strukturen, Syntax und Semantik der Logik erster Stufe, Einige klassische Resultate)
  3. Montag, 20.10.08
    Kapitel 2 fertig: Allgemeine vs. Endliche Modelltheorie, Komplexitätsklassen
    Kapitel 3 (bis Folie 13): Auswertung prädikatenlogischer Formeln "naiv", Auswertungsspiel
  4. Montag, 27.10.08
    Kapitel 3 (bis Folie 27): Spielauswertung in linearer Zeit
  5. Dienstag, 28.10.08
    Kapitel 3 fertig: Kodierung von Strukturen, Daten- und Kombikomplexität, Exkurs: Schaltkreiskomplexität, Komplexität des Auswertungsproblems der Logik erster Stufe
  6. Montag, 3.11.08
    Kapitel 4 (bis Folie 24): Modelltheoretische Beweise von Unausdrückbarkeit, Ehrenfeucht-Spiele, Beispiele, Satz von Ehrenfeucht-Fraisse
  7. Montag, 10.11.08
    Kapitel 4 (fertig): Reach ist nicht in FO: Beweis durch Ehrenfeucht-Spiel
    Kapitel 5 (bis Folie 6): Hanf-Lokalität
  8. Dienstag, 11.11.08
    Kapitel 5 (bis Folie 24): Gaifman-Lokalität, Gradbeschränkungen, 0-1-Gesetze
  9. Montag, 17.11.08
    Kapitel 5 fertig: Logische Reduktionen
    Kapitel 6 fertig: Second-Order-Logik, Satz von Fagin, Satz von Grädel
  10. Montag, 24.11.08
    Kapitel 7 (bis Folie 24): Fixpunkte, Satz von Knaster/Tarski, Fixpunktlogik, LFP charakterisiert PTIME
  11. Montag, 1.12.08
    Kapitel 7 fertig: PFP charakterisiert PSPACE, IFP, Simultane Fixpunkte, Mormalformen
    Kapitel 8 (bis Folie 4): TC-Logik (Definition und Beispiele)
  12. Montag, 8.12.08
    Kapitel 8 (bis Folie 21): LOGSPACE, Reach ist vollständig für NL, \posTC charakterisiert NL, Satz von Immerman/Szelepcsenyi
  13. Montag, 15.12. 08
    Kapitel 8 fertig: DTC und LOGSPACE, DTC vs. posDTC
    Kapitel 9 (bis Folie 18): Logik-Kierarchien, DTC <TC, DTC <posSTC, TC-Spiel
  14. Montag, 5.1.09
    Kapitel 9 (bis Folie 29): TC < LFP, Pebble-Spiel, k-Variablen-Logik, Satz von Abiteboul/Vianu (Beweis noch nicht beendet)
  15. Dienstag, 6.1.09
    Kapitel 9 fertig: Beweis des Satzes von Abiteboul/Vianu
    Kapitel 10 (bis Folie 9, und 16-18): Ajtai-Fagin-Spiel, Graphzusammenhang nicht in EMSO ausdrückbar, Invariante Formeln, Logik für P
  16. Montag, 12.1.09
    Kapitel 10 fertig: Graphzusammenhang nicht in <-invariantem EMSO ausdrückbar, Logische Charakterisierung von Schaltkreisklassen
    Kapitel 11 (bis Folie 4): Beispiele für FO-definierbare Sprachen
  17. Dienstag, 13.1.09
    Kapitel 11 (bis Folie 19): Satz von Büchi/Elgot und Trakhtenbrot, Anwendungen
  18. Montag, 19.1.09
    Kapitel 11 fertig: Entscheidbarkeit der Presburger-Arithmetik durch Automaten, Charakterisierung der FO-definierbaren regulären Sprachen durch sternfreie reguläre Ausdrücke und Aperiodizität
  19. Dienstag, 20.1.09
    Kapitel 12 (bis Folie 15): Transitionssysteme, (Reguläre) Linearzeiteigenschaften, Safetyeigenschaften, Livenesseigenschaften
  20. Montag, 26.1.09
    Kapitel 12 fertig: omega-reguläre Sprachen, Büchi-Automaten, LTL, Model Checking für LTL, Komplexität von LTL
  21. Dienstag, 27.1.09
    Kapitel 13 (bis Folie 20). parametrisierte Komplexität, Satz von Seese, Reguläre Baumsprachen
  22. Montag, 2.2.09
    Kapitel 13 (bis Folie 40): Baumzerlegungen, Satz von Courcelle (mit Anwendungen), parametrisierte Reduktionen, paraNP, XP
  23. Dienstag, 3.2.09
    Kapitel 13 fertig: W[P], W-Hierarchie, A-Hierarchie