*Parameterized Complexity Theory*by Jörg Flum and Martin Grohe, 2006.*Elements of Finite Model Theory*by Leonid Libkin, 2004.*Finite Model Theory*by Heinz-Dieter Ebbinghaus and Jörg Flum, 1995

- Graphs and logic: automata and logics, pathwidth, treewidth, Courcelle's theorem, locality of First Order logic, locally bounded treewidth.
- EF games: expressive power of FO, MSO.
- Turing machines and finite models: Fagin's theorem and NP, ordered structures, fixed point logics, a logic for PTIME?
- Zero-one laws.

- 6 January: MSO on graphs, statement of Courcelle's theorem, MSO on strings, Büchi, Elgot and Trakhtenbrot Theorem. References: chapters 4.2 and 10.1 of [1].
- 8 January: Continuation of BET theorem. Path decompositions and their properties. References: chapters 10.1 and 11.1 of [1].
- 13 January: Interpreting a graph on its path decomposition. References: chapter 11.4 of [1].
- 20 January: Interpreting a graph on its path decomposition, MSO transductions. References: chapter 11.4 of [1].
- 22 January: introduction to tree automata, conclusion of proof of Courcelle's theorem. References: chapters 10.2 and 11.4 of [1].
- 27 January: introduction to Ehrenfeucht-Fraïssé games. References: chapters 3.1-3.3 of [2].
- 29 January: rank-k m-types. References: chapter 3.4 of [2].
- 3 February: proof of Ehrenfeucht-Fraïssé theorem. References: chapter 3.5 of [2].
- 5 February: some classical results of First Order logic. References: chapter 0(C) of [3].
- 17 February: Gaifman's locality theorem. References: chapter 1 of [3].
- 3 March: Model checking first order sentences on classes of graphs with bounded local treewidth. References: chapter 12.2 of [1].
- 5 March: Trakhtenbrot's theorem and failure of completeness. References: chapter 9.1 of [2].
- 10 March: Fagin's theorem and NP. References: chapter 9.2 of [2].
- 12 March: introduction to fixed points of operators on sets. References: chapter 10.1 of [2].
- 17 March: fixed point logics. References: chapter 10.2 of [2].
- 19 March: simultaneous fixed points. References: chapter 10.3 of [2].
- 24 March: LFP captures PTIME on ordered structures. References: chapter 10.4 of [2].
- 26 March: Zero-one law for FO on graphs. References: Joshua Horowitz's notes, available here.
- 31 March: Zero-one law for LFP on graphs. References: chapters 11.1, 11.2, 12.1 and 12.2 of [2].
- 2 April: MSO games and types. References: chapter 7.2 of [2].
- 7 April: existential and universal fragments of MSO. References: chapter 7.3 of [2].
- 9 April: expressive power of existential MSO, Hanf's locality of FO. References: chapters 7.3, 4.2 and 4.3 of [2].