کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421792 | 684963 | 2011 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Closed Fragment of IL is PSPACE Hard
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we consider IL0, the closed fragment of the basic interpretability logic IL. We show that we can translate GL1, the one variable fragment of Gödel-Löbʼs provabilty logic GL, into IL0. Invoking result on the PSPACE completeness of GL1 we obtain the PSPACE hardness of IL0.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 278, 3 November 2011, Pages 47-54
Journal: Electronic Notes in Theoretical Computer Science - Volume 278, 3 November 2011, Pages 47-54