An Algebraic Approach to General Boolean Constraint Problems
Title | An Algebraic Approach to General Boolean Constraint Problems |
Publication Type | Technical Report |
Year of Publication | 1990 |
Authors | Guesgen, H. Werner, & Ladkin P. |
Other Numbers | 572 |
Abstract | We consider an algebraic approach to the statement and solution of general Boolean constraint satisfaction problems (CSPs). Our approach is to consider partial valuations of a constraint network (including the relational constraints themselves) as sets of partial functions, with the operators of join and projection. We formulate all the usual concepts of CSPs in this framework, including k-consistency, derived constraints, and backtrack-freeness, and formulate an algorithm scheme for k-consistency which has the path-consistency scheme in [LadMad88.2] as a special case. This algebra may be embedded in the cylindric algebra of Tarski [HeMoTa71, 85], via the embedding of [ImiLip84], and a connection with relational database operations. CSPs are shown to correspond to conjunctive queries in relational database theory, and we formulate a notion of equivalence of CSPs with hidden variables, following [ChaMer76, Ull80], and show that testing equivalence is NP-hard. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-90-08.pdf |
Bibliographic Notes | ICSI Technical Report TR-90-008 |
Abbreviated Authors | H. W. Guesgen and P. B. Ladkin |
ICSI Publication Type | Technical Report |