کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4662564 | 1633544 | 2007 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Derivability in certain subsystems of the Logic of Proofs is -complete
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
منطق ریاضی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The Logic of Proofs realizes the modalities from traditional modal logics with proof polynomials, so an expression □F becomes t:F where t is a proof polynomial representing a proof of or evidence for F. The pioneering work on explicating the modal logic S4 is due to S. Artemov and was extended to several subsystems by V. Brezhnev. In 2000, R. Kuznets presented a algorithm for deducibility in these logics; in the present paper we will show that the deducibility problem is -complete. (The analogous problem for traditional modal logics is PSPACE-complete.) Both Kuznets’s work and the present results make assumptions on the values of proof constants.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 145, Issue 3, March 2007, Pages 223-239
Journal: Annals of Pure and Applied Logic - Volume 145, Issue 3, March 2007, Pages 223-239