## FMT: summary

Below is a summary of the course on Finite Model Theory, with links to relevant materials. Here is some more literature on the subject. Here are the exam topics.

 18 February: introduction and computational complexity of FO 27 February: Fagin’s theorem 6 March: Fixed Point Logics: IFP, TCL 13 March: Ehrenfeucht-Fraisse games [Chapter 3 from Libkin’s book] 20 March: 0-1 laws [Chapter 12, Sections 1-3 from Libkin’s book] 27 March: Partial Fixed Point logic and the Abiteboul-Vianu theorem 3 April, 10 April: Gaifman and Hanf locality [Chapter 2, Sections 4,5 from the Ebbinghaus-Flum book] 17 April: Easter break 25 April: logics for PTime and the CFI construction 1 May: spring break 8 May: Logics for Ptime, canonisation and isomorphism 15 May: Conjunctive Queries – [see also chapter 5 from these lecture notes for the Theory of Databases] 22 May: Constraint Satisfaction Problems – basics and basics of the algebraic approach [see also chapters 1,2 from this exposition by Manuel Bodirsky] 29 May, 5 June: Computing with Acyclic Joins [chapter 6 from these lecture notes for the Theory of Databases]

## FMT 8b: Constraint Satisfaction Problems – algebraic approach

In this post, we continue the study of the complexity of Constraint Satisfaction Problems (see previous post). We introduce an algebraic tool for this, namely, polymorphisms.

## FMT: tematy egzaminacyjne

Poniżej jest lista tematów egzaminacyjnych obowiązująca na egzaminie ustnym z Teorii Modeli Skończonych.

## FMT 8a: Constraint Satisfaction Problems

We discuss the basics of Constraint Satisfaction Problems (CSPs). Some basic facts concerning the algebraic approach to CSPs are presented in the next post.

## FMT 7: Conjunctive Queries

This post discusses some basic facts about conjunctive queries, the containment problem, and minimization.

## FMT 6: capturing PTime and canonisation

In this post, we consider the question of the existence of a logic corresponding to PTime more formally, and we relate it to the graph isomorphism problem. This post is loosely based on a chapter of Martin Grohe’s book.

## FMT 5: the CFI theorem

Recall the following result from this post.

Theorem (Immerman-Vardi).  Over linearly-ordered, finite structures, IFP is equally expressive as PTime.

In this post we will prove the theorem of Cai, Fürer and Immerman that the above result does not extend to the class of all finite structures. Using a geometric argument, we show that the logic IFP+C cannot determine solvability of systems of linear equations modulo $2$.

## FMT 4: Logics for PSpace and the Abiteboul-Vianu theorem

In the meantime, we studied Ehrenfeucht-Fraisse games, finite variable logic, k-pebble games and 0-1 laws. The relevant material is in Libkin’s book, in chapters 3, 11.1, 11.2 and 12.

Now we come back to the study of logics capturing known complexity classes.

# Continue reading FMT 4: Logics for PSpace and the Abiteboul-Vianu theorem

## FMT 3: Fixpoint Logics

In view of Fagin’s Theorem, a the following question arises.

The big question. Does there exist a logic $\Ll$ such that a property of finite structures is definable in the logic $\Ll$ if and only if it is in PTime?

We will see that fixpoint logic offers a partial answer to this question.