Publication Details
Title: An Algebraic Approach to General Boolean Constraint Problems
Author: H. W. Guesgen and P. B. Ladkin
Group: ICSI Technical Reports
Date: March 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-08.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-90-008
Bibliographic Reference:
H. W. Guesgen and P. B. Ladkin. An Algebraic Approach to General Boolean Constraint Problems. ICSI Technical Report TR-90-008, March 1990
Author: H. W. Guesgen and P. B. Ladkin
Group: ICSI Technical Reports
Date: March 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-08.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-90-008
Bibliographic Reference:
H. W. Guesgen and P. B. Ladkin. An Algebraic Approach to General Boolean Constraint Problems. ICSI Technical Report TR-90-008, March 1990