![](/images/graphics-bg.png)
On the Complexities of Selected Satisfiability and Equivalence Queries over Boolean Formulas and Inclusion Queries over Hulls
المؤلف
المصدر
Journal of Applied Mathematics and Decision Sciences
العدد
المجلد 2009، العدد 2009 (31 ديسمبر/كانون الأول 2009)، ص ص. 1-18، 18ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2009-07-20
دولة النشر
مصر
عدد الصفحات
18
التخصصات الرئيسية
الملخص EN
This paper is concerned with the computational complexities of three types of queries, namely, satisfiability, equivalence, and hull inclusion.
The first two queries are analyzed over the domain of CNF formulas, while hull inclusion queries are analyzed over continuous and discrete sets defined by rational polyhedra.
Although CNF formulas can be represented by polyhedra over discrete sets, we analyze them separately on account of their distinct structure.
In particular, we consider the NAESAT and XSAT versions of satisfiability over HornCNF, 2CNF, and Horn⊕2CNF formulas.
These restricted families find applications in a number of practical domains.
From the hull inclusion perspective, we are primarily concerned with the question of checking whether two succinct descriptions of a set of points are equivalent.
In particular, we analyze the complexities of integer hull inclusion over 2SAT and Horn polyhedra.
Hull inclusion problems are important from the perspective of deriving minimal descriptions of point sets.
One of the surprising consequences of our work is the stark difference in complexities between equivalence problems in the clausal and polyhedral domains for the same polyhedral structure.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Subramani, K.. 2009. On the Complexities of Selected Satisfiability and Equivalence Queries over Boolean Formulas and Inclusion Queries over Hulls. Journal of Applied Mathematics and Decision Sciences،Vol. 2009, no. 2009, pp.1-18.
https://search.emarefa.net/detail/BIM-502829
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Subramani, K.. On the Complexities of Selected Satisfiability and Equivalence Queries over Boolean Formulas and Inclusion Queries over Hulls. Journal of Applied Mathematics and Decision Sciences No. 2009 (2009), pp.1-18.
https://search.emarefa.net/detail/BIM-502829
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Subramani, K.. On the Complexities of Selected Satisfiability and Equivalence Queries over Boolean Formulas and Inclusion Queries over Hulls. Journal of Applied Mathematics and Decision Sciences. 2009. Vol. 2009, no. 2009, pp.1-18.
https://search.emarefa.net/detail/BIM-502829
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-502829
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
![](/images/ebook-kashef.png)
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر
![](/images/kashef-image.png)