Details
| Original language | English |
|---|---|
| Pages (from-to) | 59-66 |
| Number of pages | 8 |
| Journal | Information processing letters |
| Volume | 96 |
| Issue number | 2 |
| Publication status | Published - 31 Oct 2005 |
Abstract
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.
Keywords
- Boolean constraints, Closure properties, Combinatorial problems, Computational complexity
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- Signal Processing
- Computer Science(all)
- Information Systems
- Computer Science(all)
- Computer Science Applications
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Information processing letters, Vol. 96, No. 2, 31.10.2005, p. 59-66.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Bases for Boolean co-clones
AU - Böhler, Elmar
AU - Reith, Steffen
AU - Schnoor, Henning
AU - Vollmer, Heribert
N1 - Funding Information: ✩ Supported in part by DFG grant Vo 630/5-1. * Tel.: +49-931-888-6669; Fax: +49-931-888-6661. E-mail addresses: boehler@informatik.uni-wuerzburg.de (E. Böhler), streit@streit.cc (S. Reith), schnoor@thi.uni-hannover.de (H. Schnoor), vollmer@thi.uni-hannover.de (H. Vollmer).
PY - 2005/10/31
Y1 - 2005/10/31
N2 - 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.
AB - 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.
KW - Boolean constraints
KW - Closure properties
KW - Combinatorial problems
KW - Computational complexity
UR - http://www.scopus.com/inward/record.url?scp=27544431529&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2005.06.003
DO - 10.1016/j.ipl.2005.06.003
M3 - Article
AN - SCOPUS:27544431529
VL - 96
SP - 59
EP - 66
JO - Information processing letters
JF - Information processing letters
SN - 0020-0190
IS - 2
ER -