کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873826 | 1440706 | 2018 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
ترجمه فارسی عنوان
خصوصیات کلاسهای پیچیدگی چندجملهای و نمادین در محاسبات لامبدا ابتدایی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی محاسباتی نامتجانس، منطق خطی، محاسبات لامبدا،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper an implicit characterization of the complexity classes k-EXP and k-FEXP, for kâ¥0, is given, by a type assignment system for a stratified λ-calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic (ELL), and the hierarchy of complexity classes k-EXP is characterized by a hierarchy of types.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 261, Part 1, August 2018, Pages 55-77
Journal: Information and Computation - Volume 261, Part 1, August 2018, Pages 55-77
نویسندگان
Patrick Baillot, Erika De Benedetti, Simona Ronchi Della Rocca,