EPSRC logo

Details of Grant 

EPSRC Reference: GR/L92549/01
Title: PROGRAM SCHEMES AND FINITE MODEL THEORY
Principal Investigator: Stewart, Professor IA
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Mathematics
Organisation: University of Leicester
Scheme: Standard Research (Pre-FEC)
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 resource-bounded 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 polynomial-time), in the absence of built-in relations, would immediately yield a database query language expressing exactly the polynomial-time 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 fixed-point 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 well-known Generalised Hex problem.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic 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