| EPSRC Reference: |
GR/R22704/01 |
| Title: |
Algebraic Structural Methods and Complexity of Constraint Satisfaction: An Initial Study |
| Principal Investigator: |
Jeavons, Professor PG |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
University of Oxford |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
12 March 2001 |
Ends: |
11 June 2001 |
Value (£): |
10,170
|
| EPSRC Research Topic Classifications: |
| Algebra & Geometry |
Fundamentals of Computing |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
This proposal is for a Visiting Fellowship for a period of 3 months to enable Dr Krokhin of Ural State University, Russia, to work with Dr Peter Jeavons at the University of Oxford. Dr Krokhin is a specialist in algebra, and especially the theory of clones, and this project is designed to explore how results from algebraic clone theory can be used in the study of the family of computational problems known as constraint satisfaction problems . This family of problems has been widely studied in computer science, and there have been many attempts to characterise restrictions on the general problem which make it possible to solve it efficiently. It appears that further progress with this difficult question could be made by using results from algebraic clone theory, and this project will begin to explore that possibility. One novel feature of the approach is that it includes both finite constraint satisfaction problems (such as graph colouring problems, and scheduling problems) and infinite constraint satisfaction problems (such as temporal and spatial reasoning problems). By taking an abstract, algebraic approach we hope to find a framework which incorporates both types of problems (which have traditionally been studied separately) and so obtain a better description of the computational complexity of these important problems.
|
|
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.ox.ac.uk |