کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874110 | 1441023 | 2018 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Constant runtime complexity of term rewriting is semi-decidable
ترجمه فارسی عنوان
پیچیدگی زمانبندی بازنویسی اصطلاح نیمه قابل حل است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی محاسباتی، تصمیم گیری، روش های رسمی، صحت برنامه، دوره بازنویسی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove that it is semi-decidable whether the runtime complexity of a term rewrite system is constant. Our semi-decision procedure exploits that constant runtime complexity is equivalent to termination of a restricted form of narrowing, which can be examined by considering finitely many start terms. We implemented our semi-decision procedure in the tool AProVE to show its efficiency and its success for systems where state-of-the-art complexity analysis tools fail.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 139, November 2018, Pages 18-23
Journal: Information Processing Letters - Volume 139, November 2018, Pages 18-23
نویسندگان
Florian Frohn, Jürgen Giesl,