| EPSRC Reference: |
GR/M98050/01 |
| Title: |
EFFICIENT FRAGMENTS OF TRANSITIVE CLOSURE LOGIC |
| Principal Investigator: |
Alechina, Dr N |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
School of Computer Science |
| Organisation: |
University of Nottingham |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
27 March 2001 |
Ends: |
26 June 2004 |
Value (£): |
47,375
|
| 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 |
|
Many problems in computer science have been to do with analysing graphs. A logical language which can be used to represent and solve those problems should contain first order logic (a binary predicate and quantifiers)and, in addition, some form of recursion to express properties like reachability and connectivity. We study first order logic extended with transitive closure operator (FO(TC)).There is a trade-off between expressive power of language and its efficiency: how much time does it take to evaluate a query written in this language. For FO(TC) formulas, the upper bound on this time is polynomial. The purpose of this project is to characterise fragments of FO(TC) which are expressive enough to be useful for interesting applications and at the same time admit linear time query evaluation.We are also interested in decidable fragments of FO(TC)
|
|
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.nottingham.ac.uk |