کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950723 | 1364302 | 2017 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of validity for propositional dependence logics
ترجمه فارسی عنوان
پیچیدگی اعتبار برای منطق وابستگی گزاره
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the complexity of the validity problems of propositional dependence logic, modal dependence logic, and extended modal dependence logic. We show that the validity problem for propositional dependence logic is NEXPTIME-complete. In addition, we establish that the corresponding problems for modal dependence logic and extended modal dependence logic coincide. We show containment in NEXPTIMENP, whereas NEXPTIME-hardness follows from the propositional case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 253, Part 2, April 2017, Pages 224-236
Journal: Information and Computation - Volume 253, Part 2, April 2017, Pages 224-236
نویسندگان
Jonni Virtema,