| EPSRC Reference: |
EP/F069154/1 |
| Title: |
Arithmetic Circuits in Mathematical Logic |
| Principal Investigator: |
Pratt-Hartmann, Dr I |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
University of Manchester, The |
| Scheme: |
Standard Research |
| Starts: |
17 July 2008 |
Ends: |
16 September 2009 |
Value (£): |
40,055
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
Logic & Combinatorics |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
21 Apr 2008
|
ICT Prioritisation Panel (April 2008)
|
Announced
|
|
|
Summary on Grant Application Form |
|
One of the central concerns of Theoretical Computer Science is to understand the expressiveness of different formalisms for specifying computational processes. What computations can be specified in one formalism that cannot be specified in some other? What is the cost of translating from a specification in one formalism to a specification in another, when such a translation is possible? What is the computational complexity of determining various properties of computations specified a given formalism?The research proposed here aims to contribute to our understanding of arithmetic circuits---a formalism for specifying computations on sets of natural numbers---focusing primarily on issues of expressive power and computational complexity. Despite their naturalness apparent simplicity, arithmetic circuits pose many unsolved mathematical problems, with intimate connections to a variety of topics in mathematical 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: |
http://www.cs.man.ac.uk/~ipratt/ |
| Further Information: |
|
| Organisation Website: |
http://www.man.ac.uk |