%0 Journal Article %1 Apt2000 %A Apt, Krzysztof R. %D 2000 %J New Trends in Constraints %K kiwi %P 91--107 %T Some Remarks on Boolean Constraint Propagation %X 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).

@article{Apt2000, abstract = {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).}, added-at = {2008-11-14T13:33:38.000+0100}, author = {Apt, Krzysztof R.}, biburl = {https://www.bibsonomy.org/bibtex/287ef4dfad0b6491932fa9dc20d9dda60/fraktalek}, citeulike-article-id = {3508722}, interhash = {e3111f693a0e6fa962d88a613970d077}, intrahash = {87ef4dfad0b6491932fa9dc20d9dda60}, journal = {New Trends in Constraints}, keywords = {kiwi}, pages = {91--107}, posted-at = {2008-11-13 14:13:52}, priority = {2}, timestamp = {2008-11-14T13:33:40.000+0100}, title = {Some Remarks on Boolean Constraint Propagation}, year = 2000 }