Albert Atserias's lectures at the
Monday: Logic and Back-and-Forth Systems
Fall school (Sept.'07)
Finite Model Theory and Complexity
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.