No Cover Image

Journal article 1308 views 158 downloads

Cobham recursive set functions

Arnold Beckmann Orcid Logo, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen

Annals of Pure and Applied Logic, Volume: 167, Issue: 3, Pages: 335 - 369

Swansea University Author: Arnold Beckmann Orcid Logo

DOI (Published version): 10.1016/j.apal.2015.12.005

Abstract

This paper introduces the Cobham Recursive Set Functions (CRSF) as a version of polynomial time computable functions on general sets, based on a limited (bounded) form of epsilon-recursion. The approach is inspired by Cobham's classic definition of polynomial time functions based on limited rec...

Full description

Published in: Annals of Pure and Applied Logic
Published: 2015
URI: https://cronfa.swan.ac.uk/Record/cronfa25296
first_indexed 2016-01-03T01:55:54Z
last_indexed 2023-01-31T03:31:59Z
id cronfa25296
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2023-01-30T16:00:12.0026002</datestamp><bib-version>v2</bib-version><id>25296</id><entry>2016-01-02</entry><title>Cobham recursive set functions</title><swanseaauthors><author><sid>1439ebd690110a50a797b7ec78cca600</sid><ORCID>0000-0001-7958-5790</ORCID><firstname>Arnold</firstname><surname>Beckmann</surname><name>Arnold Beckmann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2016-01-02</date><deptcode>MACS</deptcode><abstract>This paper introduces the Cobham Recursive Set Functions (CRSF) as a version of polynomial time computable functions on general sets, based on a limited (bounded) form of epsilon-recursion. The approach is inspired by Cobham's classic definition of polynomial time functions based on limited recursion on notation. The paper introduces a new set composition function, and a new smash function for sets which allows polynomial increases in the ranks and in the cardinalities of transitive closures. It bootstraps CRSF, proves closure under (unbounded) replacement, and proves that any CRSF function is embeddable into a smash term. When restricted to natural encodings of binary strings as hereditarily finite sets, the CRSF functions define precisely the polynomial time computable functions on binary strings. Prior work of Beckmann, Buss and Friedman and of Arai introduced set functions based on safe-normal recursion in the sense of Bellantoni-Cook. This paper proves an equivalence between our class CRSF and a variant of Arai's predicatively computable set functions.</abstract><type>Journal Article</type><journal>Annals of Pure and Applied Logic</journal><volume>167</volume><journalNumber>3</journalNumber><paginationStart>335</paginationStart><paginationEnd>369</paginationEnd><publisher/><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic/><keywords>Set function, Polynomial time, Cobham Recursion, Smash function, Hereditarily finite sets, Rudimentary function</keywords><publishedDay>28</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2015</publishedYear><publishedDate>2015-12-28</publishedDate><doi>10.1016/j.apal.2015.12.005</doi><url/><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm/><funders/><projectreference/><lastEdited>2023-01-30T16:00:12.0026002</lastEdited><Created>2016-01-02T17:55:48.5702377</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Arnold</firstname><surname>Beckmann</surname><orcid>0000-0001-7958-5790</orcid><order>1</order></author><author><firstname>Sam</firstname><surname>Buss</surname><order>2</order></author><author><firstname>Sy-David</firstname><surname>Friedman</surname><order>3</order></author><author><firstname>Moritz</firstname><surname>M&#xFC;ller</surname><order>4</order></author><author><firstname>Neil</firstname><surname>Thapen</surname><order>5</order></author></authors><documents><document><filename>0025296-02012016192637.pdf</filename><originalFilename>paperoneRevisedAPALNov2015.pdf</originalFilename><uploaded>2016-01-02T19:26:37.9200000</uploaded><type>Output</type><contentLength>365207</contentLength><contentType>application/pdf</contentType><version>Author's Original</version><cronfaStatus>true</cronfaStatus><embargoDate>2016-12-28T00:00:00.0000000</embargoDate><copyrightCorrect>true</copyrightCorrect></document></documents><OutputDurs/></rfc1807>
spelling 2023-01-30T16:00:12.0026002 v2 25296 2016-01-02 Cobham recursive set functions 1439ebd690110a50a797b7ec78cca600 0000-0001-7958-5790 Arnold Beckmann Arnold Beckmann true false 2016-01-02 MACS This paper introduces the Cobham Recursive Set Functions (CRSF) as a version of polynomial time computable functions on general sets, based on a limited (bounded) form of epsilon-recursion. The approach is inspired by Cobham's classic definition of polynomial time functions based on limited recursion on notation. The paper introduces a new set composition function, and a new smash function for sets which allows polynomial increases in the ranks and in the cardinalities of transitive closures. It bootstraps CRSF, proves closure under (unbounded) replacement, and proves that any CRSF function is embeddable into a smash term. When restricted to natural encodings of binary strings as hereditarily finite sets, the CRSF functions define precisely the polynomial time computable functions on binary strings. Prior work of Beckmann, Buss and Friedman and of Arai introduced set functions based on safe-normal recursion in the sense of Bellantoni-Cook. This paper proves an equivalence between our class CRSF and a variant of Arai's predicatively computable set functions. Journal Article Annals of Pure and Applied Logic 167 3 335 369 Set function, Polynomial time, Cobham Recursion, Smash function, Hereditarily finite sets, Rudimentary function 28 12 2015 2015-12-28 10.1016/j.apal.2015.12.005 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2023-01-30T16:00:12.0026002 2016-01-02T17:55:48.5702377 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Arnold Beckmann 0000-0001-7958-5790 1 Sam Buss 2 Sy-David Friedman 3 Moritz Müller 4 Neil Thapen 5 0025296-02012016192637.pdf paperoneRevisedAPALNov2015.pdf 2016-01-02T19:26:37.9200000 Output 365207 application/pdf Author's Original true 2016-12-28T00:00:00.0000000 true
title Cobham recursive set functions
spellingShingle Cobham recursive set functions
Arnold Beckmann
title_short Cobham recursive set functions
title_full Cobham recursive set functions
title_fullStr Cobham recursive set functions
title_full_unstemmed Cobham recursive set functions
title_sort Cobham recursive set functions
author_id_str_mv 1439ebd690110a50a797b7ec78cca600
author_id_fullname_str_mv 1439ebd690110a50a797b7ec78cca600_***_Arnold Beckmann
author Arnold Beckmann
author2 Arnold Beckmann
Sam Buss
Sy-David Friedman
Moritz Müller
Neil Thapen
format Journal article
container_title Annals of Pure and Applied Logic
container_volume 167
container_issue 3
container_start_page 335
publishDate 2015
institution Swansea University
doi_str_mv 10.1016/j.apal.2015.12.005
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 1
active_str 0
description This paper introduces the Cobham Recursive Set Functions (CRSF) as a version of polynomial time computable functions on general sets, based on a limited (bounded) form of epsilon-recursion. The approach is inspired by Cobham's classic definition of polynomial time functions based on limited recursion on notation. The paper introduces a new set composition function, and a new smash function for sets which allows polynomial increases in the ranks and in the cardinalities of transitive closures. It bootstraps CRSF, proves closure under (unbounded) replacement, and proves that any CRSF function is embeddable into a smash term. When restricted to natural encodings of binary strings as hereditarily finite sets, the CRSF functions define precisely the polynomial time computable functions on binary strings. Prior work of Beckmann, Buss and Friedman and of Arai introduced set functions based on safe-normal recursion in the sense of Bellantoni-Cook. This paper proves an equivalence between our class CRSF and a variant of Arai's predicatively computable set functions.
published_date 2015-12-28T03:50:59Z
_version_ 1821375945131425792
score 11.04748

Similar Items