Computation on finite structures and Lindstroem logics, zero-one laws and dynamic logics

Iain Stewart

(Leicester)

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 ordered, i.e., we are essentially dealing with 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. It will last approximately 45 minutes.

I am also Co-ordinator of MathFIT. The broad aim of the Mathematics for Information Technology (MathFIT) 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. In the final 15 minutes of my seminar I shall explain the MathFIT initiative and the opportunities for funding.
Thursday 15th November 2001, 14:00
Robert Recorde Room
Department of Computer Science