کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876044 | 690189 | 2015 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A new order-theoretic characterisation of the polytime computable functions
ترجمه فارسی عنوان
ویژگی جدید نظریه نظری توابع محاسباتی چندگانه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
دوره بازنویسی، تجزیه و تحلیل پیچیدگی، پیچیدگی محاسباتی نامتجانس، اتوماسیون،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We propose a new order-theoretic characterisation of the class of polytime computable functions. To this avail we define the small polynomial path order (sPOPâ for short). This termination order entails a new syntactic method to analyse the innermost runtime complexity of term rewrite systems fully automatically: for any rewrite system compatible with sPOPâ that employs recursion up to depth d, the (innermost) runtime complexity is polynomially bounded of degree d. This bound is tight. Thus we obtain a direct correspondence between a syntactic (and easily verifiable) condition of a program and the asymptotic worst-case complexity of the program.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 585, 20 June 2015, Pages 3-24
Journal: Theoretical Computer Science - Volume 585, 20 June 2015, Pages 3-24
نویسندگان
Martin Avanzini, Naohi Eguchi, Georg Moser,