Some Remarks on Boolean Constraint Propagation
| dc.creator | Apt, Krzysztof R. | |
| dc.date | 2000-03-28 | |
| dc.date.accessioned | 2026-07-07T03:16:08Z | |
| dc.date.available | 2026-07-07T03:16:08Z | |
| dc.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). | |
| dc.description | 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 | |
| dc.identifier | https://arxiv.org/abs/cs/0003080 | |
| dc.identifier | http://arxiv.org/abs/cs/0003080 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30237 | |
| dc.subject | Artificial Intelligence | |
| dc.subject | D.3.2;D.3.3 | |
| dc.title | Some Remarks on Boolean Constraint Propagation | |
| dc.type | text |