Auf Grund der aktuellen Situation wird die Veranstaltung in diesem Semester bis auf Weiteres online durchgeführt.
In diesem Logbuch werden regelmäßig Informationen dazu bereit gestellt, welche Lektüre von allen Teilnehmer*innen bis zum nächsten "Vorlesungstermin" selbständig durchgearbeitet werden soll. Die "Vorlesungstermine" (Di+Do 11-13 Uhr) werden über Zoom als Online-Treffen durchgeführt (die Zugangsdaten werden über Moodle bereit gestellt), in denen Fragen zur Lektüre gestellt werden können und das in der Lektürearbeit erarbeitete Wissen weiter vertieft wird.
Das erste Online-Treffen fand am Dienstag, 28.04.20 statt.
-
bis Di, 28.04.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
-
Lehrbuch [L]: Kapitel 1.
-
Viele weitere Beispiele zur Bedeutung der Logik in der Informatik finden
sich in dem Artikel "On the unusual effectiveness of
logic in computer science" von Halpern, Harper, Immerman, Kolaitis, Vardi
und Vianu, Bulletin of Symbolic Logic 7(2):213-236 (2001). Eine
Vorabversion des Artikels finden Sie hier.
-
bis Do, 30.04.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
-
Lehrbuch [L]: Kapitel 2.1, 2.2 und 9.1.
-
bis Di, 05.05.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 9.1, 7.1 und 7.4
- Lehrbuch [FG]: Kapitel 10.1.
-
bis Do, 07.05.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [FG]: Kapitel 10.1.
- Lehrbuch [L]: Kapitel 7.4 (Beweis
mittels "MSO-Typen").
- Lehrbuch [Howard Straubing: Finite Automata, Formal Logic, and Circuit
Complexity. Birkhäuser, 1994]: Kapitel III.1 (der Beweis
nutzt eine eingeschränkte Syntax und eine andere Definition der Semantik, die in Kapitel II des Buchs eingeführt werden).
- Informationen zu Anwendungen der "Automatentheoretischen Methode" (analog zum Beweis der "schwierigen Richtung" des Satzes von Büchi finden sich in Section 6 des Artikels "On the unusual effectiveness of
logic in computer science" von Halpern, Harper, Immerman, Kolaitis, Vardi
und Vianu, Bulletin of Symbolic Logic 7(2):213-236 (2001) (eine
Vorabversion des Artikels finden Sie hier).
- Einen Überblick und weitere
Literaturhinweise gibt auch die Arbeit "Logik und Automaten: ein echtes Dreamteam" von Björklund, Martens, Schweikardt und Schwentick, Informatik Spektrum 33(5): 452-461 (2010) LINK
-
bis Di, 12.05.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 7.4 und Kapitel 9.2.
-
bis Do, 14.05.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 9.2.
-
bis Di, 19.05.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 9.2.
- In [Grädel] finden sich
u.a. Details zum Beweis des Satzes von Grädel
-
bis Di, 26.05.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 3.2 bis 3.5.
- Lehrbuch [EF]: Kapitel 2.1 bis 2.3.
-
bis Do, 28.05.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 3.2 und 7.5.
- Lehrbuch [EF]: Kapitel 6.4.
-
bis Di, 02.06.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 7.5 und Kapitel 4.1 bis 4.3.
- Lehrbuch [EF]: Kapitel 6.4 und Kapitel 2.4 und Kapitel 12.3 ("Logical Reductions").
-
bis Do, 04.06.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 4.1 bis 4.3.
- Lehrbuch [EF]: Kapitel 2.4.
-
bis Di, 09.06.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 4.1 bis 4.3 und Kapitel 7.3 (zur Anwendung des Satzes von Hanf bzw. der Hanf-Lokalität von FO zum Nachweis, dass Graph-Zusammenhang nicht EMSO-definierbar ist)
- Lehrbuch [EF]: Kapitel 2.4 (siehe Proposition 2.4.5)
-
bis Do, 11.06.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 7.3 (zur Anwendung des Satzes von Hanf bzw. der Hanf-Lokalität von FO zum Nachweis, dass Graph-Zusammenhang nicht EMSO-definierbar ist) und Kapitel 3.5
- Lehrbuch [EF]: Kapitel 2.4 (siehe Proposition 2.4.5) und Kapitel 2.3
-
bis Di, 16.06.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 12.1 und 12.2
-
bis Do, 18.06.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 12.1 und 12.2
-
bis Di, 23.06.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 8.2 und 11.1-11.2
-
bis Do, 25.06.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 11.1-11.2 und 12.1-12.3
- In [K] finden
sich viele weitere Informationen zu infinitären Logiken, u.a. auch
Details zum Beweis des Satzes von de Rougemont
-
bis Di, 30.06.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 10.1 und 10.2
-
bis Do, 02.07.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 10.1-10.3
-
bis Di, 07.07.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 10.1-10.4
-
bis Do, 09.07.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 10.4
- In [G] finden sich
viele Details zum Thema Fixpunklogiken.
-
bis Di, 14.07.2020:
Arbeiten Sie Folgendes durch:
Ergänzende Lektüre:
- Lehrbuch [L]: Kapitel 10.4
- In [G] finden sich
viele Details zum Thema Fixpunklogiken.
-
bis Do, 16.07.2020:
Arbeiten Sie Folgendes durch:
-
Kapitel 3.1.4 "The Quest for a Logic Capturing Polynomial Time" im Buch
Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, Martin Grohe, Lecture Notes in Logic, Volume 47. Cambridge University Press, 2017.
LINK
Ergänzende Lektüre:
- Martin Grohe, The quest for a logic capturing PTIME.
In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.267-271, 2008.
- Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, Martin Grohe, Lecture Notes in Logic, Volume 47. Cambridge University Press, 2017.
LINK
