No Cover Image

Journal article 1304 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
Tags: Add Tag
No Tags, Be the first to tag this record!
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.
Keywords: Set function, Polynomial time, Cobham Recursion, Smash function, Hereditarily finite sets, Rudimentary function
College: Faculty of Science and Engineering
Issue: 3
Start Page: 335
End Page: 369

Similar Items