کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331937 | 686981 | 2005 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bases for Boolean co-clones
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Bases for Boolean co-clones Bases for Boolean co-clones](/preview/png/10331937.png)
چکیده انگلیسی
The complexity of various problems in connection with Boolean constraints, like, for example, quantified Boolean constraint satisfaction, have been studied recently. Depending on what types of constraints may be used, the complexity of such problems varies. A very interesting observation of the recent past has been that the thus derived classification of constraints can be explained with the help of universal algebra. More precisely, the difficulty of such a constraint problem often depends on the co-clone the constraints are from. A co-clone is a set of Boolean relations that is closed under very natural closure operations. Nearly all these co-clones can be generated by said operators out of a finite set of relations, a so-called base. Knowing a, preferably simple, base for each co-clone can therefore be of great value when studying the complexity of Boolean constraint problems, since this knowledge reduces the infinitely many cases of equivalent problems to a single one-the constraint satisfaction problem for this base. In this paper we give a finite and simple base for every Boolean co-clone, where this is possible. We give evidence that the presented bases are as easy as possible.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 96, Issue 2, 31 October 2005, Pages 59-66
Journal: Information Processing Letters - Volume 96, Issue 2, 31 October 2005, Pages 59-66
نویسندگان
Elmar Böhler, Steffen Reith, Henning Schnoor, Heribert Vollmer,