An Isaac Newton Institute Programme

Logic and Algorithms

Model theory on well-behaved finite structures

12th June 2006

Author: Anuj Dawar (Cambridge)

Abstract

The early days of finite model theory saw a variety of results establishing that the model theory of the class of finite structures is not well-behaved. Recent work has shown that considering subclasses of the class of finite structures allows us to recover some good model-theoretic behaviour. This appears to be especially true of some classes that are known to be algorithmically well-behaved. I will review some results in this area and explore the connection between logic and algorithms.