Some Remarks on Boolean Constraint Propagation
Abstract
Description
We study here the well-known propagation rules for Boolean constraints. First we propose a simple notion of completeness for sets of such rules and establish a completeness result. Then we show an equivalence in an appropriate sense between Boolean constraint propagation and unit propagation, a form of resolution for propositional logic.
Subsequently we characterize one set of such rules by means of the notion of hyper-arc consistency introduced in (Mohr and Masini 1988). Also, we clarify the status of a similar, though different, set of rules introduced in (Simonis 1989a) and more fully in (Codognet and Diaz 1996).
14 pages. To appear in: New Trends in Constraints, Papers from the Joint ERCIM/Compulog-Net Workshop Cyprus, October 25-27, 1999. Springer-Verlag Lecture Notes in Artificial Intelligence
14 pages. To appear in: New Trends in Constraints, Papers from the Joint ERCIM/Compulog-Net Workshop Cyprus, October 25-27, 1999. Springer-Verlag Lecture Notes in Artificial Intelligence