کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6876046 690189 2015 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Characterizing polynomial time complexity of stream programs using interpretations
ترجمه فارسی عنوان
مشخص کردن پیچیدگی زمان چندجمله ای برنامه های جریان با استفاده از تفسیر ها
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , , ,