CLP(Set) is a member in the CLP family, where each variable can have a set as its value. Although a number of languages are named CLP(Set), they are quite different. Some languages allow intentional and infinite sets, and some languages allows user-defined function symbols in set constraints. The CLP(Set) language in B-Prolog only allows finite sets of ground terms. A set constant is either the empty set {}, or {T1,T2,...,Tn}, where each Ti (i=1,2,...,n) is a ground term.

We reuse some of the operators in Prolog and CLP(FD) (e.g., /\, \/, \, #=, and #\=), and introduce several new operators to the language in order to denote set operations and set constraints. Since most of the operators are generic, and since their interpretation depends on the types of constraint expressions, users have to provide information for the system to infer the types of expressions.

The type of a variable can either be known from its domain declaration, or it can be inferred from its context. The domain of a set variable is declared by a call as follows:

     V :: L..U
where V is a variable, and L and U are two set constants that respectively indicate the lower and upper bounds of the domain. The lower bound contains all definite elements that are known to be in V, and the upper bound contains all possible elements that may be in V. All definite elements must be possible. In other words, L must be a subset of U. If this is not the case, then the declaration fails. The special set constant {I1..I2} represents the set of integers in the range from I1 to I2, inclusive. For example: The notation is extended, such that V can be a list of variables. Therefore, the call
     [X,Y,Z] :: {}..{1..3}
declares three set variables.

The following primitives are provided to test and to access set variables:

The following two predicates are provided for converting between sets and lists:

A set expression is defined recursively as follows: (1) a constant set; (2) a variable; (3) a composite expression in the form of S1 \/ S2, S1 /\ S2, S1 \ S2, or \ S1, where S1 and S2 are set expressions. The operators \/ and /\ represent union and intersection, respectively. The binary operator \ represents difference, and the unary operator \ represents complement. The complement of a set \ S1 is equivalent to U \ S1, where U is the universal set. Since the universal set of a constant is unknown, in the expression \ S1, S1 must be a variable whose universal set has been declared.

The syntax for finite-domain constraint expressions is extended in order to allow the expression #S, which denotes the cardinality of the set that is represented by the set expression S.

Let S, S1, and S2 be set expressions, and let E be a term. A set constraint takes one of the following forms:

Boolean constraint expressions are extended in order to allow set constraints. For example, the constraint

     (E #<- S1) #=> (E #<- S2)
says that, if E is a member of S1, then E must also be a member of S2.

Constraint propagation is used to maintain the consistency of set constraints, like it is used for finite and Boolean constraints. However, constraint propagation alone is inadequate for finding solutions for many problems. The divide-and-conquer or relaxation method must be used to find solutions to a system of constraints. The call

finds a value for V, either by enumerating the values in V's domain, or by splitting the domain. The instantiation of variables usually triggers related constraint propagators.

Neng-Fa Zhou 2013-01-25