کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426385 | 686047 | 2016 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bounded Combinatory Logic and lower complexity
ترجمه فارسی عنوان
منطق ترکیبی محدود و پیچیدگی کمتر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
منطق ترکیبی؛ طبقه بندی؛ پیچیدگی محاسباتی ضمنی. زمان و فضای چندجمله ای؛ منطق خطی نرم
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We introduce a stratified version of Combinatory Logic1 in which there are two classes of terms called player and opponent such that the class of player terms is strictly contained in the class of opponent terms. We show that the system characterizes Polynomial Time in a similar way to Soft Linear Logic. With the addition of explicit “lazy” products to the player terms and various notions of distributivity, we obtain a characterization of Polynomial Space. This paper is an expanded version of the abstract presented at DICE 2013.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 248, June 2016, Pages 215–226
Journal: Information and Computation - Volume 248, June 2016, Pages 215–226
نویسندگان
Brian F. Redmond,