Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

Aktuelles

• 16.01.24: am Mittwoch, den 17.01.24 findet kein Seminar-Vortrag statt; der Vortrag wird verschoben auf den 31.01.24.
• 22.11.23: Ergänzung zu Thema 4: Eine etwas leichter zugängliche Einführung des Begriffs "Transduktion" findet sich in den Kapiteln 1.7.1 und 1.7.2 (Seiten 59-67) des Buchs "Graph Structure and Monadic Second-Order Logic — a Language Theoretic Approach" von Bruno Courcelle und Joost Engelfriet (Cambridge University Press 2012; eine Vorabversion findet sich hier: [LINK]).
• Die Vorbesprechung und Themenvergabe fand in der zweiten Vorlesungswoche, am Mittwoch, den 25.10.2023, um 13:30-15:00 Uhr in Raum 3.408 (Johann von Neumann-Haus) statt.
• Das Seminar wird in Präsenz durchgeführt.
• Die Latex-Vorlage, mit der die Seminar-Ausarbeitungen erstellt werden sollen, finden Sie hier: [Link]

Thema

Anhand von Originalarbeiten und ergänzender Literatur werden im Seminar aktuelle Themen der Theoretischen Informatik, insbesondere der Logik und Komplexitätstheorie erarbeitet. Ziele sind das Kennenlernen neuer Forschungsergebnisse der Theoretischen Informatik, 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 Masterstudiengang, die sich im Bereich Theoretische Informatik spezialisieren wollen. Die Teilnahme am Seminar setzt sehr gute und zumindest in einem der o.g. Bereiche auch tiefer gehende Kenntnisse der Theoretischen Informatik voraus.

Ort & Zeit

Zeit und Raum

mittwochs, 13:30-15:00 Uhr im Johann von Neumann-Haus (Rudower Chaussee 25), Raum 3.408.

Dozentin:

Prof. Dr. Nicole Schweikardt

Themen

Dieses Seminar richtet sich an Studierende, die bereits das Modul "Logik und Komplexität" absolviert haben oder sich anderweitig vergleichbare Vorkenntnisse erarbeitet haben.

Konkrete Themen, die im Seminar behandelt werden:

• Thema 1: Der erste Seminartermin (Vorbesprechung, Organisatorisches) fand am Mittwoch, den 25.10.23 statt.
• Thema 2: A note on the size of prenex normal forms. Frederik Harwath, Inf. Process. Lett. 116(7): 443-446 (2016). Termin: 8.11.23
• Thema 3: Kapitel 2.3 des Buchs [Grohe] (Seiten 22-32): Syntax und Semantik verschiedener Logiken, mit Fokus auf IFP+C, inkl vieler Beispiele. Termin: 08.11.23
• Thema 4: Kapitel 2.4 des Buchs [Grohe] (Seiten 32-39):
  Transduktionen (Begriffsdefinition und viele Beispiele). Termin: 22.11.23
  Eine etwas leichter zugängliche Einführung des Begriffs "Transduktion" findet sich in den Kapiteln 1.7.1 und 1.7.2 (Seiten 59-67) des Buchs "Graph Structure and Monadic Second-Order Logic — a Language Theoretic Approach" von Bruno Courcelle und Joost Engelfriet (Cambridge University Press 2012; eine Vorabversion findet sich hier: [LINK])
• Thema 5: Kapitel 3.1.4 des Buchs [Grohe] (Seiten 49-51): Die Suche nach einer "Logik für PTIME". Termin: 06.12.23
• Thema 6: Kapitel 3.2 und Anfang von Kapitel 3.3 des Buchs [Grohe] (Seiten 51-61): definierbare Ordnungen und definierbare Kanonisierungen. Termin: 13.12.23
• Thema 7: Rest von Kapitel 3.3 des Buchs [Grohe] (Seiten 61-71): definierbare Kanonisierungen. Termin: 20.12.23
• Thema 8: Kapitel 3.4 des Buchs [Grohe] (Seiten 71-79): Pebble-Spiele und Logiken mit beschränkter Anzahl von Variablen. Termin: 10.01.24
• Thema 9: Anfang von Kapitel 3.5 des Buchs [Grohe] (Seiten 79-86): Isomorphie-Test und der Weisfeiler-Leman-Algorithmus. Termin: 17.01.24 31.01.24
• Thema 10: Rest von Kapitel 3.5 des Buchs [Grohe] (Seiten 86-93): Isomorphie-Test und der Weisfeiler-Leman-Algorithmus. Termin: 31.01.24
• Thema 11: Erste Hälfte der folgenden Arbeit: An optimal lower bound on the number of variables for graph identifications. Jin-yi Cai, Martin Fürer und Neil Immerman. Combinatorica 12(4): 389-410 (1992). Seiten 389-400. Termin: 24.01.24
• Thema 12: Zweite Hälfte der folgenden Arbeit: An optimal lower bound on the number of variables for graph identifications. Jin-yi Cai, Martin Fürer und Neil Immerman. Combinatorica 12(4): 389-410 (1992). Seiten 400-410. Termin: 31.01.24
• Thema 13: Anfang von Kapitel 5 des Buchs [Libkin] (Seiten 67-77): Ordnungs-invariante Anfragen (Teil 1). Termin: 07.02.23
• Thema 14: Rest von Kapitel 5 des Buchs [Libkin] (Seiten 77-83): Ordnungs-invariante Anfragen (Teil 2). Termin: 14.02.23

Literatur