Logik in der Informatik
Prof. Dr. Nicole Schweikardt

Vorlesung Ausgewählte Kapitel der Logik: Lokalität

Wintersemester 2019/20

Aktuelles Einführung Inhalte Logbuch Termine Prüfung Literatur Links

Aktuelles

Am Dienstag, den 28.01.2020 findet die Vorlesung nicht statt.
Die Eröffnungsvorlesung fand am Dienstag, den 15.10.2019 statt.
Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

Einführung

Die mathematische Logik beschäftigt sich mit den grundlegenden Eigenschaften von formalen Systemen und Sprachen, insbesondere der Ausdrucksstärke von formalen Sprachen und Beweissystemen sowie den Möglichkeiten und Grenzen des automatischen Schließens. In dieser Vorlesung werden ausgewählte Kapitel der mathematischen Logik und deren Anwendungen in der Informatik im Kontext von Lokalitätsresultaten behandelt.

Themen der Vorlesung sind u.a. die Sätze von Gaifman und Hanf und die Anwendung von Lokalitätsresultaten zum Nachweis von Nicht-Ausdrückbarkeitsresultaten und zum Beweis von algorithmischen Meta-Theoremen.

Die Vorlesung richtet sich an fortgeschrittene Studierende in einem Masterstudiengang, die sich im Bereich der Logik spezialisieren wollen. Voraussetzung für die Teilnahme an der Veranstaltung sind Kenntnisse, die in der Vorlesung "Logik in der Informatik" vermittelt werden.

Inhalte

Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und möglicherweise verändert.

Kapitel 0: Einleitung und Grundbegriffe (handschriftliche Notizen)
Kapitel 1: Hanf-Normalform und Hanf-Lokalität (handschriftliche Notizen)
Kapitel 2: Feferman-Vaught Zerlegungen (handschriftliche Notizen)
Kapitel 3: Gaifman-Normalform und Gaifman-Lokalität (handschriftliche Notizen: Teil 1, Teil 2)
Kapitel 4: Baumzerlegungen und Baumweite von Graphen (handschriftliche Notizen)
Kapitel 5: Anwendung der Gaifman-Normalform zum Nachweis eines algorithmischen Metatheorems — Model-Checking für FO und FO+MOD auf Klassen von beschränkter lokaler Baumweite (handschriftliche Notizen: Teil 1, Teil 2)
Kapitel 6: Untere Schranken für die Größe von Formeln in Normalform (handschriftliche Notizen)

Beachten Sie: In den Vorlesungsstunden wird hauptsächlich an der Tafel gearbeitet. Alle behandelten Inhalte sind für die Veranstaltung wesentlich und daher auch dann prüfungsrelevant, wenn sie nicht in den auf den Webseiten erhältlichen Materialien enthalten sind.
Zur Vorbereitung auf eine Prüfung wird dringend empfohlen, das gesamte in den Vorlesungsstunden vermittelte Material durchzuarbeiten. Es ist daher wichtig, dass Sie sich während der Vorlesungs- und Übungsstunden Notizen machen.

Logbuch

Hier finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

Termine

Vorlesung: Dienstags 15:00-17:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'305 und
Donnerstags 15:00-17:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'305
Dozentin: Prof. Dr. Nicole Schweikardt

Prüfung

Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungsstunden vermittelte Material durchzuarbeiten.

Die Modulabschlussprüfung wird durch eine mündliche Prüfung abgelegt. Termine für mündliche Modulabschlussprüfungen können nach Vereinbarung bei Frau Pergl angefragt werden.

Literatur

[EFT] H.-D. Ebbinghaus, J. Flum, W. Thomas, Einführung in die mathematische Logik, Spektrum Akademischer Verlag, 4. Auflage, 1996

[S-LI] N. Schweikardt, Skript zur Vorlesung "Logik in der Informatik" im Wintersemester 2017/18, Humboldt-Universität zu Berlin. LINK.

[L] Leonid Libkin, Elements of Finite Model Theory. Springer-Verlag, 2004. Die für die Vorlesung relevanten Teile des Buchs sind hier unter dem mit "Download table of contents and a sample chapter" beschrifteten Link erhältlich.

[EF] Heinz-Dieter Ebbinghaus und Jörg Flum, Finite Model Theory. Springer-Verlag, 2. Auflage, 1999.

[D] Reinhard Diestel, Graphentheorie. Springer-Verlag, 3. Auflage, 2006. LINK.

[FG] Jörg Flum und Martin Grohe, Parameterized Complexity. Springer-Verlag, 2006.

[FG01] Markus Frick und Martin Grohe, Deciding First-Order Properties of Locally Tree-Decomposable Structures. In Journal of the ACM, Vol. 48, No. 6, November 2001, pp. 1184-1206. LINK.

[KS17] Dietrich Kuske und Nicole Schweikardt, First-order logic with counting. In Proc. LICS 2017. LINK.
Eine ausführlichere Vorabversion findet sich bei ArXiv unter der Nummer CoRR abs/1703.01122. LINK.

[BKS17] Christoph Berkholz, Jens Keppeler und Nicole Schweikardt, Answering FO+MOD Queries Under Updates on Bounded Degree Databases. In Proc. ICDT 2017. LINK.
Eine ausführlichere Vorabversion findet sich bei ArXiv unter der Nummer CoRR abs/1702.08764. LINK.

[KS18] Dietrich Kuske und Nicole Schweikardt, Gaifman normal forms for counting extensions of first-order logic. In Proc. ICALP 2018. LINK.

[GS18] Martin Grohe und Nicole Schweikardt, First-Order Query Evaluation with Cardinality Conditions. In Proc. PODS 2018, pp. 253-266. LINK.
Eine ausführlichere Vorabversion findet sich bei ArXiv unter der Nummer CoRR abs/1707.05945. LINK.

[DGKS07] Anuj Dawar, Stephan Kreutzer, Martin Grohe und Nicole Schweikardt, Model Theory Makes Formulas Large. In Proc. ICALP 2017, pp. 913-924. LINK.
Eine ausführlichere Vorabversion findet sich hier.

[HKS13] Lucas Heimberg, Dietrich Kuske und Nicole Schweikardt, An Optimal Gaifman Normal Form Construction for Structures of Bounded Degree. In Proc. LICS 2013, pp. 63-72. LINK.

Links

[LICS] IEEE Symposium on Logic in Computer Science (LICS)

[EACSL] European Association for Computer Science Logic (EACSL)

[Highlights] Highlights of Logic, Games and Automata

Last modified: 21.01.2020
Nicole Schweikardt

[EFT]	H.-D. Ebbinghaus, J. Flum, W. Thomas, Einführung in die mathematische Logik, Spektrum Akademischer Verlag, 4. Auflage, 1996
[S-LI]	N. Schweikardt, Skript zur Vorlesung "Logik in der Informatik" im Wintersemester 2017/18, Humboldt-Universität zu Berlin. LINK.
[L]	Leonid Libkin, Elements of Finite Model Theory. Springer-Verlag, 2004. Die für die Vorlesung relevanten Teile des Buchs sind hier unter dem mit "Download table of contents and a sample chapter" beschrifteten Link erhältlich.
[EF]	Heinz-Dieter Ebbinghaus und Jörg Flum, Finite Model Theory. Springer-Verlag, 2. Auflage, 1999.
[D]	Reinhard Diestel, Graphentheorie. Springer-Verlag, 3. Auflage, 2006. LINK.
[FG]	Jörg Flum und Martin Grohe, Parameterized Complexity. Springer-Verlag, 2006.
[FG01]	Markus Frick und Martin Grohe, Deciding First-Order Properties of Locally Tree-Decomposable Structures. In Journal of the ACM, Vol. 48, No. 6, November 2001, pp. 1184-1206. LINK.
[KS17]	Dietrich Kuske und Nicole Schweikardt, First-order logic with counting. In Proc. LICS 2017. LINK. Eine ausführlichere Vorabversion findet sich bei ArXiv unter der Nummer CoRR abs/1703.01122. LINK.
[BKS17]	Christoph Berkholz, Jens Keppeler und Nicole Schweikardt, Answering FO+MOD Queries Under Updates on Bounded Degree Databases. In Proc. ICDT 2017. LINK. Eine ausführlichere Vorabversion findet sich bei ArXiv unter der Nummer CoRR abs/1702.08764. LINK.
[KS18]	Dietrich Kuske und Nicole Schweikardt, Gaifman normal forms for counting extensions of first-order logic. In Proc. ICALP 2018. LINK.
[GS18]	Martin Grohe und Nicole Schweikardt, First-Order Query Evaluation with Cardinality Conditions. In Proc. PODS 2018, pp. 253-266. LINK. Eine ausführlichere Vorabversion findet sich bei ArXiv unter der Nummer CoRR abs/1707.05945. LINK.
[DGKS07]	Anuj Dawar, Stephan Kreutzer, Martin Grohe und Nicole Schweikardt, Model Theory Makes Formulas Large. In Proc. ICALP 2017, pp. 913-924. LINK. Eine ausführlichere Vorabversion findet sich hier.
[HKS13]	Lucas Heimberg, Dietrich Kuske und Nicole Schweikardt, An Optimal Gaifman Normal Form Construction for Structures of Bounded Degree. In Proc. LICS 2013, pp. 63-72. LINK.

[LICS]	IEEE Symposium on Logic in Computer Science (LICS)
[EACSL]	European Association for Computer Science Logic (EACSL)
[Highlights]	Highlights of Logic, Games and Automata