Albert Atserias's lectures at the
Fall school (Sept.'07)

Finite Model Theory and Complexity

Monday: Logic and Back-and-Forth Systems

1.1 Structures, definability and fragments.
1.2 Quantifier-rank and types.
1.3 Back-and-forth systems and games.
1.4 Composition lemmas.


Tuesday: Locality of First-order Logic

2.1 Neigborhoods and Hanf locality.
2.2 Gaifman Locality Theorem.
2.3 Some applications: inexpressibility results and checking sentences on structures of bounded degree.


Wednesday: Inexpressibility Results

3.1 Separating existential from universal MSO.
3.2 Inexpressibility in the presence of order.
3.3 Schwentick's Theorem.


Thursday: Treewidth and Checking Logical Sentences

4.1. Checking logical sentences.
4.2. Thick trees.
4.3. Courcelle's Theorems.
4.4. Some applications: feedback vertex set, checking sentences on planar structures.

Bibliography:

  • H.-D. Ebbinghaus and J. Flum. Finite Model Theory. 2nd edition. Springer 1999.

  • J. Flum and M. Grohe. Parameterized Complexity Theory. Springer 2006.

  • E. Grädel, Ph. G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Vardi, I. Venema, S. Weinstein. Finite Model Theory and Its Applications. Springer 2007.

  • N. Immerman. Descriptive Complexity. Springer 1999.

  • L. Libkin. Elements of Finite Model Theory. Springer 2004.

    Disclaimer: No relationship with Springer.