10.9.10.1 Definitions

For constraint store S, variable X, and finite domain R:

• D(X,S) denotes the domain of X in S.
• (X in R)(S) denotes the extension of S where D(X,S) has been intersected with R.

The following definitions, adapted from [Van Hentenryck et al. 95], define important notions of consistency and entailment of constraints wrt. stores.

A ground constraint is true if it holds and false otherwise.

A constraint C is domain-consistent wrt. S iff, for each variable Xi and value Vi in D(Xi,S), there exist values Vj in D(Xj,S), 1 <= j <= n /\ i != j, such that C(V1,…,Vn) is true.

A constraint C is domain-entailed by S iff, for all values Vj in D(Xj,S), 1 <= j <= n, C(V1,…,Vn) is true.

Let D’(X,S) denote the interval [min(D(X,S)),max(D(X,S))].

A constraint C is bounds-consistent wrt. S iff, for each variable Xi, there exist values Vj and Wj in D’(Xj,S), 1 <= j <= n, i != j, such that C(V1,…,min(D(Xi,S)),…,Vn) and C(W1,…,max(D(Xi,S)),…,Wn) are both true.

A constraint C is bounds-entailed by S iff, for all values Vj in D’(Xj,S), 1 <= j <= n, C(V1,…,Vn) is true.

Finally, a constraint is domain-disentailed (bounds-disentailed) by S iff its negation is domain-entailed (bounds-entailed) by S.