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

(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