کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876046 | 690189 | 2015 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Characterizing polynomial time complexity of stream programs using interpretations
ترجمه فارسی عنوان
مشخص کردن پیچیدگی زمان چندجمله ای برنامه های جریان با استفاده از تفسیر ها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper provides a criterion based on interpretation methods on term rewrite systems in order to characterize the polynomial time complexity of second order functionals. For that purpose it introduces a first order functional stream language that allows the programmer to implement second order functionals. This characterization is extended through the use of exp-poly interpretations as an attempt to capture the class of Basic Feasible Functionals (bff). Moreover, these results are adapted to provide a new characterization of polynomial time complexity in computable analysis. These characterizations give a new insight on the relations between the complexity of functional stream programs and the classes of functions computed by Oracle Turing Machine, where oracles are treated as inputs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 585, 20 June 2015, Pages 41-54
Journal: Theoretical Computer Science - Volume 585, 20 June 2015, Pages 41-54
نویسندگان
Hugo Férée, Emmanuel Hainry, Mathieu Hoyrup, Romain Péchoux,