<Chapter id="fset.tutorial.intro"> <Title/Introduction/

<Para><Title/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 <Math>{\cal U} = \{0,\ldots,sup\}</Math>. The value of
<Math>sup</Math> is determined by the actual implementation and in
&moz3 it is <Math>&fs_sup; = 2^{27}-2</Math><Note foot>The reason for
this value is as follows: efficient integers (so-called <Em/small
integers/ in &moz3;) occupy 28 bits. Hence the biggest positive
integer is <Math>2^{27}-1</Math>. To be able to represent the
cardinality of a set by a small integer, the biggest element of a set
is determined to <Math>2^{27}-2</Math>.</Note>.

<Para><Title/Set Constraints/
A basic set constraint approximates a set value <Math>S</Math> in
three different ways:

<List>

<Item> Constraining the lower bound by set <Math>s</Math>: <Math>s
\subseteq S</Math>. The lower bound contains all elements that are at
least contained in the set value.

<Item> Constraining the upper bound by set <Math>s</Math>: <Math>S
\subseteq s</Math>. The upper bound contains all elements that are at
most contained in the set value. 

<Item> Constraining the cardinality of a set by a finite domain
interval <Math>\{n,\ldots,m\}</Math>: <Math>n \le \#S \le
m.</Math>. The cardinality constraint determines the minimal and
maximal number of elements allowed to be contained in the set.

</List>

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. 

<P>
Non-basic set constraints, as intersection <Math>\cap</Math>, union
<Math>\cup</Math>, disjointness <Math>\|</Math>, and the like, are
provided as propagators. For details on the provided set propagators
see <Ptr.Extern to="ozdoc:system" key="chapter.fs">.

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

<Para><Title/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 <Em>integers</Em> is exploited. For
example, a finite domain can be constrained to be the minimal &resp;
maximal element of a set (see <Ptr.Extern to="ozdoc:system"
key="chapter.fs"> for details on <<FS.int.min>> &resp;
<<FS.int.max>>). Another possibility is to match the elements of a set
of a certain cardinality <Math>c</Math> with a tuple of <Math>c</Math>
finite domains (see <Ptr.Extern to="ozdoc:system" key="chapter.fs">
for details on <<FS.int.match>>) that is used in <Ptr
to="fset.examples.steiner">.

<Para><Title/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 <Math>n \in S \vee n \notin S</Math>. The following
figure illustrates that.

<PICTURE.extern display to="setdistr.gif" id="setdistr.pic" type=GIF>

<P>

<!-- ********************************************************************** -->

</Chapter>

