| Kommentar |
Viele algorithmische Probleme lassen sich durch logische Formeln beschreiben. Dabei besteht ein enger Zusammenhang zwischen der Kompliziertheit der Formeln und der Berechnungskomplexität der Probleme. Dieser Zusammenhang spielt in verschiedenen Bereichen der Informatik eine Rolle, zum Beispiel in der Theorie formaler Sprachen, der Datenbanktheorie, der Komplexitätstheorie und im Zusammenhang mit automatischer Verifikation.
Themen dieser Vorlesung sind beispielsweise:
- Erweiterungen der Logik erster Stufe: Logik zweiter Stufe, Fixpunktlogiken
- Automatentheorie und Logik: logische Charakterisierung der regulären Sprachen (z.B. die Sätze von Buchi und Doner, Thatcher & Wright)
- deskriptive Komplexitätstheorie: logische Charakterisierungen von Komplexitätsklassen (z.B. die Sätze von Fagin und Immerman & Vardi)
- Endliche Modelltheorie: Trennungsresultate zwischen logisch definierten Klassen endlicher Strukturen, 0-1-Gesetze
Ziel dieser Veranstaltung ist, den Zusammenhang zwischen der logischen Beschreibbarkeit und der Berechnungskomplexität von Problemen zu verstehen.
Voraussetzung für die Teilnahme an der Veranstaltung sind solide Grundkenntnisse in den Bereichen Logik und Komplexitätstheorie.
|
