Some Remarks on Boolean Constraint Propagation
<|reference_start|>Some Remarks on Boolean Constraint Propagation: 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).<|reference_end|>
@article{apt2000some,
    title={Some Remarks on Boolean Constraint Propagation},
    author={Krzysztof R. Apt},
    journal={arXiv preprint arXiv:cs/0003080},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0003080},
    primaryClass={cs.AI}
}