Theory Seminar

Finite model theory, complexity theory and program schemes

Iain Stewart

Department of Mathematics & Computer Science
University of Leicester

4pm 7th May 2002
Room 2511, JCMB, King's Buildings

The speaker is Co-ordinator of MathFIT. The broad aim of the Mathematics for Information Technology initiative is to support, through research grants, visiting fellowships, networks, workshops and summer schools, high-quality interdisciplinary research in areas at the interface between mathematics and computer science. It is jointly sponsored by the Engineering and Physical Sciences Research Council (EPSRC) and the London Mathematical Society (LMS), and began in the summer of 1996, was subsequently expanded in spring 2000 and will run until 2003.

Following his research talk (ca. 45 min), the speaker will give on overview of MathFIT (ca. 15 min).

---

Abstract

Finite model theory is all about what one can say about classes of finite structures (such as graphs, strings and so on) using logic; and computational complexity is all about what one can compute on finite inputs within given resources. There is a very strong link between finite model theory and computational complexity theory (exemplified by Fagin's Theorem that a problem is in NP if and only if it can be defined in existential second-order logic). Often, this link is strongest when the finite structures are (essentially) strings: on arbitrary finite structures, the link between resource-bounded computation and logical definability is nowhere near as clear-cut. In this introductory talk, I will introduce this subject, known as descriptive complexity, and I will also introduce models of computation, program schemes, for computing on arbitrary finite structures, and show how a consideration of these models can lead to new results in finite model theory and descriptive complexity. The talk will be introductory in nature and suitable for a general audience.