Cobham recursive set functions
- Submitting institution
-
Swansea University / Prifysgol Abertawe
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 25296
- Type
- D - Journal article
- DOI
-
10.1016/j.apal.2015.12.005
- Title of journal
- Annals of Pure and Applied Logic
- Article number
- -
- First page
- 335
- Volume
- 167
- Issue
- 3
- ISSN
- 0168-0072
- Open access status
- Out of scope for open access requirements
- Month of publication
- December
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
-
- Research group(s)
-
-
- Citation count
- 1
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Computability over natural numbers has been successfully extended to robust notions of computability on sets. This paper develops an analogous, robust extension of computational complexity to arbitrary sets. It invents new set operations which are suitable to express polynomial growth on arbitrary sets which are of general interest. Using those it provides a set function algebra which under natural encoding of finite strings corresponds to polynomial-time. Work has led to set axiom characterisations (World Scientific Lecture Notes Series, Sets and Computations, 55-116, 2017) and invention of generalisations of circuits to arbitrary sets (Computability, Volume 8, 67-98, 2018).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -