کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10321210 | 659280 | 2005 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The complexity of model checking for propositional default logics
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The complexity of model checking for propositional default logics The complexity of model checking for propositional default logics](/preview/png/10321210.png)
چکیده انگلیسی
We analyze the complexity of deciding whether a propositional interpretation is a model of a default theory for some of the variants of default logic presented in the literature: Reiter's, justified, constrained, rational, and cumulative. We prove that all the analyzed variants are Σ2p-complete in the general case, and remains so even if all defaults are prerequisite-free and seminormal. Cumulative default logic is also Σ2p-complete even if all defaults are normal and prerequisite-free. The other semantics are Î2p[logn]-complete and coNP-complete if all defaults are normal and prerequisites are allowed or not, respectively.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Data & Knowledge Engineering - Volume 55, Issue 2, November 2005, Pages 189-202
Journal: Data & Knowledge Engineering - Volume 55, Issue 2, November 2005, Pages 189-202
نویسندگان
Paolo Liberatore, Marco Schaerf,