کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4661596 1344846 2016 35 صفحه PDF ندارد دانلود رایگان
عنوان انگلیسی مقاله
Cobham recursive set functions
ترجمه فارسی عنوان
توابع مجموعه بازگشتی Cobham
کلمات کلیدی
توابع مجموعه . زمان چند جمله ای؛بازگشت Cobham . عملکرد سر و صدا ؛ محدود ارثی ؛ تابع ابتدایی
03D15; 03D20; 03E99; 68Q15Set function; Polynomial time; Cobham Recursion; Smash function; Hereditarily finite; Rudimentary function
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
چکیده انگلیسی

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 ∈-recursion. This is inspired by Cobham's classic definition of polynomial time functions based on limited recursion on notation. We introduce 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. We bootstrap CRSF, prove closure under (unbounded) replacement, and prove 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. We prove an equivalence between our class CRSF and a variant of Arai's predicatively computable set functions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 167, Issue 3, March 2016, Pages 335–369
نویسندگان
, , , , ,