FMT: summary

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

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]

Leave a Reply

Your email address will not be published. Required fields are marked *