10.35.8.1 Definitions

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 Xi and value Vi in D(Xi,S), there exist values Vj in D(Xj,S), 1 =< j =< n \land i \neq j, such that C(V1,...,Vn) is true.

A constraint C is arc-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 bound-consistent wrt. S iff, for each variable Xi, there exist values Vj and Wj in D'(Xj,S), 1 =< j =< n, i \neq 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 bound-entailed by S iff, for all values Vj in D'(Xj,S), 1 =< j =< n, C(V1,...,Vn) 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.