Kursinformation

Lehrinhalte
erststufige Logik: Lokalität und Gaifman-Normalform,
monadische zweitstufige Logik: Ausdrucksstärke auf Bäumen; Baumautomaten
Satz v. Feferman und Vaught
Graphentheorie: Planarität und Einbettbarkeit in höhere Flächen, Minoren und topologische Minoren, Separatoren, Baumzerlegungen, Baum- und Pfadweite, Graphstrukturtheorem von Robertson und Seymour
Meta-Theoreme: Satz v. Courcelle, Effiziente Auswertbarkeit von FO auf minorenabgeschlossenen Graphklassen
weitere Themen evtl.: flache Minoren, beschränkte Expansion, nirgendwo dichte Graphen, untere Schranken

Literatur
[list]
[*]Flum, Grohe: [i]Parameterized Complexity[/i], Springer Verlag
[*]Diestel: [i]Graph Theory[/i], Springer Verlag
[*]Ebbinghaus, Flum: [i]Finite Model Theory[/i], Springer Verlag
[*]B. Courcelle: Graph rewriting: an algebraic and logic approach, in: [i]Handbook of theoretical computer science (vol. B): formal models and semantics[/i], MIT Press, Cambridge, MA, USA (1990), pp. 193–242
[*]M. Grohe: Logic, graphs, and algorithms, in: J. Flum, E. Grädel, T. Wilke (Eds.), [i]Logic and Automata: History and Perspectives[/i], Amsterdam University Press, Amsterdam (2007), pp. 357–422
[*]M. Grohe and S. Kreutzer: Methods for algorithmic meta theorems, in: [i]Model Theoretic Methods in Finite Combinatorics[/i] 558 (2011): 181-206.
[/list]

Voraussetzungen
“mathematical maturity”
Previous exposition to logics and/or graph theory is desirable but not strictly necessary. Some background knowledge in computational complexity and algorithms would be a bonus.

Zusätzliche Informationen
Vertiefungsniveau

Online-Angebote
moodle