Program schemes, finite model theory and computational complexity

Finite model theory is concerned with the model theory of finite structures (such as graphs, strings etc.). It has strong connections with complexity theory and database theory. In particular, there are numerous results of the form: a problem is in some complexity class if, and only if, it can be defined in some logic. Infinite model theory has a strong mathematical tradition and there are established tools and techniques for proving undefinability results, some of which carry over to the finite setting. One hope is that these tools can be used to prove logical undefinability results which translate to complexity-theoretic lower bound results (like P is different from NP). Some of the mainstream logics of finite model theory actually arise in the more computational context of program schemes. In this talk, I will give a basic introduction to finite model theory and introduce some classes of program schemes and their relationship with some logics from finite model theory. This talk will be suitable for a broad audience.

I will follow my seminar with an explanation of the joint EPSRC/LMS initiative MathFIT (Mathematics for Information Technology) of which I am Co-ordinator. The MathFIT web-pages currently reside at: http://www.mcs.le.ac.uk/~istewart/MathFIT/MathFIT.html.