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 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:

• 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} : This fails, since {1} is not a subset of {2,3}.

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:

• 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 that is 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 following two predicates are provided for converting between sets and lists:

• set_to_list(S,L) : Converts the set S into a list.
• list_to_set(L,S) : Converts 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, 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:

• 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 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

• indomain(V):

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.