Theoretical Foundations of Value Withdrawal Explanations for Domain Reduction

AbstractSolvers on finite domains use local consistency notions to remove values from the domains. This paper defines value withdrawal explanations. Domain reduction is formalized with chaotic iterations of monotonic operators. With each operator is associated its dual which will be described by a set of rules. For classical consistency notions, there exists such a natural system of rules. The rules express value removals as consequences of other value removals. The linking of these rules inductively defines proof trees. Such a proof tree clearly explains the removal of a value (which is the root of the tree). Explanations can be considered as the essence of domain reduction