Literature | Links  

Logik und Komplexität - Endliche Modelltheorie

Lecture

Introduction

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:

Ziel dieser Veranstaltung ist, den Zusammenhang zwischen der logischen Beschreibbarkeit und der Berechnungskomplexität von Problemen zu verstehen.

Kenntnisse aus den Modulen M-LI oder M-KTH sind hilfreich.

Kürzel laut Studienordnung: M-LK, MaM-LOG-k.  Creditpoints: 8.  SWS: 3 V, 2 Ü.

Literature

[S] N. Schweikardt. Skript zur Vorlesung "Logik und Komplexität" im Sommersemester 2007, Humboldt-Universität zu Berlin. Link
[L] L. Libkin. Elements of Finite Model Theory. Springer-Verlag, 2004. Inhaltsverzeichnis und ausgewählte Kapitel des Buchs können hier heruntergeladen werden.
[EF] H.-D. Ebbinghaus und J. Flum. Finite Model Theory. Springer-Verlag, 2te Auflage, 1999.
[I] N. Immerman. Descriptive Complexity. Springer-Verlag, 1999.
[F] E. Grädel, P. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Vardi, Y. Venema und S. Weinstein. Finite Model Theory and Its Applications. Springer-Verlag, 2007.
[G] E. Grädel. Finite Model Theory and Descriptive Complexity. Kapitel 3 des Buchs [F] .
[K] P. Kolaitis. On the expressive power of logics on finite models. Kapitel 2 des Buchs [F] .
[FG] F. Flum und M. Grohe. Parameterized Complexity. Springer-Verlag, 2006.

Links

[LICS] IEEE Symposium on Logic in Computer Science (LICS)
[EACSL] European Association for Computer Science Logic (EACSL)