کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876051 | 690189 | 2015 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Applicative theories for logarithmic complexity classes
ترجمه فارسی عنوان
نظریه های کاربردی برای کلاس های پیچیدگی لگاریتمی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
خصوصیات طبقه بندی دو طبقه کلاسهای پیچیدگی نظریه های کاربردی، کلاس های پیچیدگی لگاریتمی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We present applicative theories of words corresponding to weak, and especially logarithmic, complexity classes. The theories for the logarithmic hierarchy and alternating logarithmic time formalise function algebras with concatenation recursion as main principle. We present two theories for logarithmic space where the first formalises a new two-sorted algebra which is very similar to Cook and Bellantoni's famous two-sorted algebra B for polynomial time [4]. The second theory describes logarithmic space by formalising concatenation- and sharply bounded recursion. All theories contain the predicates W representing words, and V representing temporary inaccessible words. They are inspired by Cantini's theories [6] formalising B.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 585, 20 June 2015, Pages 115-135
Journal: Theoretical Computer Science - Volume 585, 20 June 2015, Pages 115-135
نویسندگان
Sebastian Eberhard,