کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
423567 | 685256 | 2016 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Unbounded Recursion and Non-size-increasing Functions
ترجمه فارسی عنوان
بازگشت نامحدود و عملکرد افزایشی غیراندازه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We investigate the computing power of function algebras defined by means of unbounded recursion on notation. We introduce two function algebras which contain respectively the regressive logspace computable functions and the non-size-increasing logspace computable functions. However, such algebras are unlikely to be contained in the set of logspace computable functions because this is equivalent to L=P. Finally, we introduce a function algebra based on simultaneous recursion on notation for the non-size-increasing functions computable in polynomial time and linear space.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 322, 18 April 2016, Pages 197-210
Journal: Electronic Notes in Theoretical Computer Science - Volume 322, 18 April 2016, Pages 197-210