An Algebraic Approach to General Boolean Constraint Problems

TitleAn Algebraic Approach to General Boolean Constraint Problems
Publication TypeTechnical Report
Year of Publication1990
AuthorsGuesgen, H. Werner, & Ladkin P.
Other Numbers572

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 Notes

ICSI Technical Report TR-90-008

Abbreviated Authors

H. W. Guesgen and P. B. Ladkin

ICSI Publication Type

Technical Report