Node:Definitions, Next:Pitfalls of Interval Reasoning, Previous:The Constraint System, Up:The Constraint System
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 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 interval-consistent wrt. S iff, for each variable Xi and value Vi in D(Xi,S), 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 interval-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 (interval-disentailed) by S iff its negation is domain-entailed (interval-entailed) by S.