# 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.

# Praca domowa: zwartość

Poniżej jest praca domowa na piątek 23-ego maja, oraz jedno zadanie gwiazdkowe, do 10 czerwca.

# 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.

Poniżej są przykładowe rozwiązania zadań z kolokwium z JAiO z 8 maja 2014.

# Pewien język bezkontekstowy

Pojawiło się pytanie o to, czy następujący język jest bezkontekstowy:

$$L=\set{u\#v^R: uv\in D_1},$$

gdzie $D_1$ oznacza zbiór poprawnych wyrażen nawiasowych nad alfabetem $\Sigma$ składającym się z liter $($ oraz $)$.

Okazuje się, że odpowiedź brzmi tak. Autorem poniższego rozwiązania jest pan Mateusz Kopeć.

# 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$.