CLP(Set)

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 allows finite sets of ground terms only. 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 to denote set operations and set constraints. Since most of the operators are generic and their interpretation depends on the types of constraint expressions, you have to provide necessary information for the system to infer the types of expressions.

The type of a variable can be known from its domain declaration or 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 indicating respectively 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:

• V :: {}..{a,b,c} : V is subset of {a,b,c} including the empty set.
• V :: {1}..{1..3} : V is one of the sets of {1},{1,2}, {1,3}, and {1,2,3}. The set {2,3} is not a candidate value for V.
• V :: {1}..{2,3} : Fails since {1} is not a subset of {2,3}.

We extend the notation such that V can be a list of variables. So the call

     [X,Y,Z] :: {}..{1..3}

declares three set variables.

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

• clpset_var(V): V is a set variable.
• clpset_low(V,Low): The current lower bound of V is Low.
• clpset_up(V,Up): The current upper bound of V is Up.
• clpset_added(E,V): E is a definite element, i.e., an element included in the lower bound.
• clpset_excluded(E,V): E has been forbidden for V. In other words, E has been excluded from the upper bound of V.

The followint two predicates are provided for converting sets into and from lists:

• set_to_list(S,L) : Convert the set S into a list. For example,
• list_to_set(L,S) : Convert the list L into a set.

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, S1 in the expression \ S1 must be a variable whose universal set has been declared.

We extend the syntax for finite-domain constraint expressions to allow the expression #S which denotes the cardinality of the set represented by the set expression S.

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

• S1 #= S2: S1 and S2 are two equivalent sets (S1=S2).

• S1 #\= S2: S1 and S2 are two different sets (S1$\neq$S2).

• subset(S1,S2):
• clpset_subset(S1,S2): S1 is a subset of S2 (S1$\subseteq$S2). The proper subset relation S1 $\subset$ S2 can be represented as S1 subset S2 and #S1 #< #S2 where #< represents the less-than constraint on integers.

• clpset_disjoint(S1,S2):
• S1 #<> S2: S1 and S2 are disjoint (S1$\cap$S2=$\emptyset$).

• clpset_in(E,S):
• E #<- S: E is a member of S (E$\in$S). E must be ground.

• clpset_notin(E,S):
• E #<\- S: E is a not member of S (E$\notin$S). E must be ground.

Boolean constraint expressions are extended 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.

Just as for finite and Boolean constraints, constraint propagation is used to maintain the consistency of constraints. Constraint propagation alone, however, is inadequate for finding solutions for many problems. We need to use the divide-and-conquer or relaxation method to find solutions to a system of constraints. The call

• indomain(V):

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