EPSRC logo

Details of Grant 

EPSRC Reference: GR/L69596/01
Title: MODEL THEORETIC METHODS IN COMPLEXITY AND VERIFICATION
Principal Investigator: Dawar, Professor A
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Unknown
Organisation: Swansea University
Scheme: Standard Research (Pre-FEC)
Starts: 11 November 1997 Ends: 30 September 1998 Value (£): 10,541
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
The proposed research is motivated by the great similarity that is observed in the methods in use in the areas of the specification and verification of concurrent computing systems on the one hand, and descriptive complexity on the other. The research will formalise these connections by explicitly defining three translations that connect logic and structures used in one case with those in the other. The bridge between the two fields, thus established, will be used to transfer results between the two and gain a deeper understanding of both. In particular, the research will yield new insight into the computational complexity of model checking procedures for verification, answering such questions as whether there is a modal logic whose expressive power corresponds exactly to the polynomial time computable, bisimulation closed properties; as well as new results on hierarchies of descriptive complexity classes, for instance an alternation hierarchy for bounded variable fragments of fixed point logic.
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.swan.ac.uk