| EPSRC Reference: |
GR/N16129/01 |
| Title: |
AUTOMATIC GENERATION OF IMPLIED CONSTRAINTS |
| Principal Investigator: |
Frisch, Dr A |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
University of York |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 October 2000 |
Ends: |
30 September 2003 |
Value (£): |
245,039
|
| EPSRC Research Topic Classifications: |
|
| EPSRC Industrial Sector Classifications: |
| Manufacturing |
Information Technologies |
| Transport Systems and Vehicles |
No relevance to Underpinning Sectors |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
The aim of this project is to develop, analyze and evaluate methods for generating implied constraints automatically. Such methods are likely to form a vital component in the next generation of constraint satisfaction toolkits. One of the key ideas will be to combine theorem proving techniques (like ordered resolution) with constraint satisfaction algorithms. Recent studies show that implied constraints added to the model by hand can lead to significant reductions in search. However, techniques for generating such constraints automatically have not yet been developed. We intent to correct this.The proposed programme of work divided into four parts. We will first use theorem proving techniques to generate implied constraints automatically. As such techniques are likely to generate both useful and unuseful constraints, we will then develop heuristics for identifying which of the generated constraints to retain and which to discard. Having focused up to this point on the generation of implied constraints prior to the start of search, we will now consider algorithms that interleave the generation of implied constraints with the search process itself. By means of a project studentship, we will apply all these results to the domain of propositional satisfiability (SAT) and some extensions of SAT.
|
|
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.york.ac.uk |