Cobham recursive set functions

DOI10.1016/J.APAL.2015.12.005MaRDI QIDQ904151zbMATH OpenOpenAlexFDO

Authors Arnold Beckmann, Sy-David Friedman, Moritz Müller, Neil Thapen, Samuel R. Buss

Publication date 12 January 2016

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2015.12.005

zbMATH Keywords

set functionpolynomial timeCobham recursionhereditarily finiterudimentary functionsmash function

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Set theory (03E99)

Recommendations

• scientific article; zbMATH DE number 1235084
• Cobham recursive set functions and weak set theories
• scientific article; zbMATH DE number 3165537
• Recursive functions
• Farey recursive functions
• Recursive functionals
• Safe recursive set functions
• Recursive set relations
• Power set recursion

Cites work

• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 1163985 (Why is no real title available?)
• scientific article; zbMATH DE number 3999883 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• A new recursion-theoretic characterization of the polytime functions
• Cobham recursive set functions
• Predicatively computable functions on sets
• Safe recursive set functions
• The fine structure of the constructible hierarchy

Cited in

(9)

• Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 5--11, 2017
• Feasible set functions have small circuits
• Minimization and \(\mathbf{NP}\) multifunctions
• On computability and tractability for infinite sets
• On efficiency of notations for natural numbers
• Cobham recursive set functions
• Safe recursive set functions
• Cobham recursive set functions and weak set theories
• Predicatively computable functions on sets

This page was built for publication: Cobham recursive set functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q904151)