| EPSRC Reference: |
GR/L69596/02 |
| Title: |
MODEL THEORETIC METHODS IN COMPLEXITY AND VERIFICATION |
| Principal Investigator: |
Dawar, Professor A |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science and Technology |
| Organisation: |
University of Cambridge |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 October 1998 |
Ends: |
10 November 2000 |
Value (£): |
43,553
|
| 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.cam.ac.uk |