Logik und Komplexität
| Veranstaltungsnummer | 042617 |
| Titel | Logik und Komplexität (INF-MSC-509) |
| Veranstalter | Prof. Dr. Thomas Schwentick |
| Klassifikation | Vertiefungsmodul (MPO) |
| Semester | Wintersemester 2024/25 |
| SWS | 4 (3V+1Ü) |
| Kreditpunkte | 6 |
| Ort und Zeit | Vorlesung: Dienstags, 14:15 - 16:00 Uhr (Beginn: 8.10.2024) und Donnerstags (10:15-12:00 Uhr, 14-tägig ) Übung: Donnerstags 10:15 - 12:00 (14-tägig) Alle Termine in OH 12, 3.031 |
| Querverbindungen | Komplexitätstheorie, Logik |
| Voraussetzungen | GTI-Stoff wird vorausgesetzt, Komplexitätstheorie ist hilfreich, aber nicht unbedingt notwendig |
| Forschungsbereich (MPO) | Algorithmen und Komplexität |
| Materialien | Im Moodle-Arbeitsraum (Anmeldung über LSF) |
| Sprache | Folien und Videos: Englisch, Vorlesung: deutsch/englisch |
Aktuelles
The course can be taught at least partially in English.
Inhalt
Many algorithmic problems can be described by logical formulae. There is a close connection between the complexity of the formulae and the computational complexity of the problems. This connection plays a role in various areas of (theoretical) computer science, for example in the theory of formal languages, database theory, complexity theory and in the context of automatic verification. The lecture will deal with important such correspondence results and with the basic properties of the logics involved.
Individual topics:
- Foundations of first-order logic
- Expressive power of first-order logic: Ehrenfeucht games, locality, other methods
- Logic and complexity theory: second-order logic, fixed-point logics, separations
- Evaluation of logical formulae: Algorithms and complexity
- Logic and Formal Languages
- Efficient logics
Viele algorithmische Probleme lassen sich durch logische Formeln beschreiben. Dabei besteht ein enger Zusammenhang zwischen der Kompliziert der Formeln und der Berechnungskomplexität der Probleme. Dieser Zusammenhang spielt in verschiedenen Bereichen der (theoretischen) Informatik eine Rolle, zum Beispiel in der Theorie Formaler Sprachen, der Datenbanktheorie, der Komplexitätstheorie und im Zusammenhang automatischer Verifikation. Die Vorlesung wird sich mit wichtigen solchen Korrespondenz-Resultaten und mit den grundlegenden Eigenschaften der beteiligten Logiken beschäftigen.
Einzelthemen:
- Logik erster Stufe: Grundlagen
- Ausdrucksstärke der Logik erster Stufe: Ehrenfeuchtspiele, Lokalität, andere Methoden
- Logik und Komplexitätstheorie: Logik zweiter Stufe, Fixpunktlogiken, Trennungen
- Auswertung logischer Formeln: Algorithmen und Komplexität
- Logik und Formale Sprachen
- Logik und Verifikation
Literatur
Ein Folienskript wird parallel zur Vorlesung erstellt.
Weitere Literatur:
- Leonid Libkin: Elements of Finite Model Theory, Springer, 2004
- Immerman: Descriptive Complexity, Springer, 1999