Informações sobre a disciplina

Lehrinhalte
first-order logics: locality and Gaifman normal form,
monadic second-order logic: expressivity on trees, tree automata
Feferman-Vaught-Theorem
graph theory: planarity and embeddebility into higher genus surfaces, minors and topological minors, separators, tree decompositions, tree-width and path-width, graph structure theorem by Robertson and Seymour
meta theorems: Courcelle's Theorem, tractability of FO on minor closed classes
possible further topics: shallow minors, bounded expansion, nowhere dense graphs, lower bounds

Literature
[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