The constraint system is based on domain constraints and indexicals. A
domain constraint is an expression `X``::`

`I`, where
`X` is a domain variable and `I` is a nonempty set of
integers.

A set S of domain constraints is called a
store. D(X,S), the domain of X in S, is
defined as the intersection of all I such that
`X::I`

belongs to S. The store is
contradictory if the domain of some variable is empty;
otherwise, it is consistent. A consistent store S' is an
extension of a store S iff, for all variables
X, D(X,S') is contained in D(X,S).

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 arc-consistent wrt. S iff, for each variable X_i and value V_i in D(X_i,S), there exist values V_j in D(X_j,S), 1 \leq j \leq n \land i \neq j, such that C(V_1,\ldots,V_n) is true.

A constraint C is arc-entailed by S iff, for all values V_j in D(X_j,S), 1 \leq j \leq n, C(V_1,\ldots,V_n) is true.

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

A constraint C is bound-consistent wrt. S iff, for each variable X_i, there exist values V_j and W_j in D'(X_j,S), 1 \leq j \leq n, i \neq j, such that C(V_1,\ldots,\min(D(X_i,S)),\ldots,V_n) and C(W_1,\ldots,\max(D(X_i,S)),\ldots,W_n) are both true.

A constraint C is bound-entailed by S iff, for all values V_j in D'(X_j,S), 1 \leq j \leq n, C(V_1,\ldots,V_n) is true.

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

Send feedback on this subject.