کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436794 | 690040 | 2013 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Polynomial space hardness without disjunction property
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Horčík and Terui [8] show that, if a substructural logic enjoys the disjunction property, then its tautology problem is PSPACE-hard. We prove that all substructural logics in the interval between intuitionistic logic and generalized Hájek basic logic have a PSPACE-hard tautology problem, which implies that uncountably many substructural logics lacking the disjunction property have a PSPACE-hard tautology problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 467, 7 January 2013, Pages 1-11
Journal: Theoretical Computer Science - Volume 467, 7 January 2013, Pages 1-11