Abstract
The aim of this course is to present an overview of concepts, methods and results in several different topics in finite and algorithmic model theory.
Lecture 1: Definability and Undefinability
Introduction to finite model theory. Methods of proving inexpressibility of classes of finite structures. Ehrenfeucht-Fraı̈ssé games. Pebble Games. Locality Theorems. Decomposition theorems.
Lecture 2: Automata-based Methods
Monadic second-order logic (MSO) on finite words and trees. MSO on infinite words and trees. Finite graphs of bounded tree-width. Courcelle's theorem.
Lecture 3: Parameterized Model-Checking
The complexity of formula evaluation. Parameterizations by formula size and graph structure. The method of locality: first-order logic on sparse graph classes.
Lecture 4: Descriptive Complexity
Fagin and Immerman-Vardi theorems. The quest for a logic for P. Counting logics and the Cai-Fürer-Immerman construction. Restricted classes of structures. Linear algebraic problems and rank logics.
Lecture 5: Logic and Combinatorial Optimization
The role of linear programming relaxations. Graph Isomorphism and lift-and-project hierarchies. Definability through the ellipsoid method. Constraint satisfaction problems.
The first session of this mini course will take place on Monday, August 29th, 2016 11:00 am – 12:00 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 11:00 am – 12:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 9:30 am – 10:30 am; the fifth session of this mini course will take place on Friday, September 2nd, 2016 11:00 am – 12:00 pm.