1 Introduction

Set Values

Oz 3 provides finite sets of non-negative integers as first-class values and every set value is a subset of the universal set ${\cal U} = \{0,\ldots,sup\}$ . The value of sup is determined by the actual implementation and in Mozart Oz 3 it is $134217726 = 2^{27}-2$ ¹.

Set Constraints

A basic set constraint approximates a set value in three different ways:

Constraining the lower bound by set : $s \subseteq S$ . The lower bound contains all elements that are at least contained in the set value.
Constraining the upper bound by set : $S \subseteq s$ . The upper bound contains all elements that are at most contained in the set value.
Constraining the cardinality of a set by a finite domain interval $\{n,\ldots,m\}$ : $n \le \#S \le m.$ . The cardinality constraint determines the minimal and maximal number of elements allowed to be contained in the set.

A set constraint denotes a set value if either the lower is equal to the upper bound, the cardinality of the lower bound is equal to the upper bound of the cardinality constraints, or the cardinality of the upper bound is equal to the lower bound of the cardinality constraint.

Non-basic set constraints, as intersection $\cap$ , union $\cup$ , disjointness $\|$ , and the like, are provided as propagators. For details on the provided set propagators see Chapter 7 of ``System Modules''.

Set Constraint Propagation

To explain constraint propagation, assume the basic set constraints: $\emptyset \subseteq X,Y \subseteq \{1,\ldots,5\}$ and additionally the following non-basic constraints: $X \cup Y = \{1,\ldots,5\}$ and $X \| Y$ . Adding the constraints $1 \in X$ and $2 \notin Y$ yields the intermediate store $\{1\} \subseteq X \subseteq \{1,\ldots,5\}$ and $\emptyset \subseteq Y \subseteq \{1,3,4,5\}$ . The present non-basic constraints can add even more basic constraints: the disjointness constraint removes 1 from the upper bound of since 1 was added to the lower bound of . The union constraint adds 2 to the lower bound of since 2 was removed form the upper bound of . After that, propagation has reached a fixed-point and leads to $\{1,2\} \subseteq X \subseteq \{1,\ldots,5\} \wedge \emptyset \subseteq Y \subseteq \{3,4,5\}$ . Bringing the cardinality constraint $3 \le \#Y \le 5$ into play determines to $\{3,4,5\}$ since the upper bound has exactly 3 elements which is the minimal number required by the cardinality constraint. The disjointness constraint then removes 3, 4, 5 from 's upper bound and that way determines to $\{1,2\}$ .

Connecting Finite Sets and Finite Domains

Set constraints on their own are of limited use, connecting them with finite domain constraints provides much more expressivity. The straightforward way is to connect a finite set variable via the cardinality constraint to a finite domain variable. Another technique is to provide reified versions for various set constraints as containment and the like. But there are further possiblies if the fact that the elements of a set are integers is exploited. For example, a finite domain can be constrained to be the minimal resp. maximal element of a set (see Chapter 7 of ``System Modules'' for details on FS.int.min resp. FS.int.max). Another possibility is to match the elements of a set of a certain cardinality with a tuple of finite domains (see Chapter 7 of ``System Modules'' for details on FS.int.match) that is used in Chapter 2.

Distribution

Due to the fact that constraint propagation is incomplete, expectedly in case of set constraints as well, solving a problem involving set constraints requires distribution. A typical choice-point distributing a set variable is $n \in S \vee n \notin S$ . The following figure illustrates that.