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}-21.

Set Constraints

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

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 Y since 1 was added to the lower bound of X. The union constraint adds 2 to the lower bound of X since 2 was removed form the upper bound of Y. 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 Y 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 X's upper bound and that way determines X 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 c with a tuple of c 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.


1. The reason for this value is as follows: efficient integers (so-called small integers in Mozart Oz 3) occupy 28 bits. Hence the biggest positive integer is 2^{27}-1. To be able to represent the cardinality of a set by a small integer, the biggest element of a set is determined to 2^{27}-2.

Tobias Müller
Version 1.4.0 (20080702)