No Cover Image

Journal article 552 views 35 downloads

Cobham recursive set functions / Arnold, Beckmann

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

Swansea University Author: Arnold, Beckmann

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...

Full description

Published in: Annals of Pure and Applied Logic
Published: 2015
URI: https://cronfa.swan.ac.uk/Record/cronfa25296
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2016-01-03T01:55:54Z
last_indexed 2018-08-22T15:00:37Z
id cronfa25296
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2018-08-22T14:24:27.9032524</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>SCS</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&amp;apos;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&amp;apos;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/><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>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><lastEdited>2018-08-22T14:24:27.9032524</lastEdited><Created>2016-01-02T17:55:48.5702377</Created><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><action/><embargoDate>2016-12-28T00:00:00.0000000</embargoDate><copyrightCorrect>true</copyrightCorrect></document></documents></rfc1807>
spelling 2018-08-22T14:24:27.9032524 v2 25296 2016-01-02 Cobham recursive set functions 1439ebd690110a50a797b7ec78cca600 0000-0001-7958-5790 Arnold Beckmann Arnold Beckmann true false 2016-01-02 SCS 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&apos;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&apos;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 Computer Science COLLEGE CODE SCS Swansea University 2018-08-22T14:24:27.9032524 2016-01-02T17:55:48.5702377 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
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
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&apos;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&apos;s predicatively computable set functions.
published_date 2015-12-28T19:35:33Z
_version_ 1667869739460853760
score 10.900483