کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421792 684963 2011 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Closed Fragment of IL is PSPACE Hard
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The Closed Fragment of IL is PSPACE Hard
چکیده انگلیسی

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