EPSRC Reference: 
GR/L92549/01 
Title: 
PROGRAM SCHEMES AND FINITE MODEL THEORY 
Principal Investigator: 
Stewart, Professor IA 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematics 
Organisation: 
University of Leicester 
Scheme: 
Standard Research (PreFEC) 
Starts: 
01 September 1997 
Ends: 
31 December 1997 
Value (£): 
6,300

EPSRC Research Topic Classifications: 
Fundamentals of Computing 


EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
Descriptive complexity theory aims to classify problems according to how easy they are to define in a variety of logics: the traditional approach taken in (computational) complexity theory is to classify problems according to whether they can be solved using resourcebounded models of computation. Amongst other things, descriptive complexity theory seeks to give logical characterisations of complexity classes and to use methods of logic on these logical characterisations to obtain new complexity theoretic results.We feel that finite model theory currently holds the most promise of obtaining lower bound results in complexity theory, and that an understanding of the link between the descriptive complexity and the computational complexity of a problem is of fundamental importance in computer science. The novel approach theory advocated by descriptive complexity theory gives an entirely new viewpoint of complexity theory but there are also applications to more practical topics such as databases, where a logic characterising P (deterministic polynomialtime), in the absence of builtin relations, would immediately yield a database query language expressing exactly the polynomialtime queries (it is open as to whether such a query language exists). Moreover, the role of logic in computer science is firmly established and there are links between these different roles, many of which are not as yet developed, e.g. the use of fixedpoint logics in finite model theory and in the model checking of temporal properties of finite state concurrent systems. We hope that our work will appeal to other logicians and computer scientists, not necessarily just finite model theorists.The aim of the proposed research is to further examine:a) hierarchies of program schemes and related logics;b) the logical expressibility and complexity of variants of the wellknown Generalised Hex problem.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.le.ac.uk 