/usr/share/mozart/doc/fst/node1.html is in mozart-doc 1.4.0-8ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>1 Introduction</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="index.html">- Up -</A></TD><TD><A href="node2.html#fset.examples.steiner">Next >></A></TD></TR></TABLE><DIV id="fset.tutorial.intro"><H1><A name="fset.tutorial.intro">1 Introduction</A></H1><P class="margin">Set Values</P><P> Oz 3 provides finite sets of non-negative integers as first-class values and every set value is a subset of the universal set <IMG alt="{\cal U} = \{0,\ldots,sup\}" src="latex1.png">. The value of <IMG alt="sup" src="latex2.png"> is determined by the actual implementation and in Mozart Oz 3 it is <IMG alt="134217726 = 2^{27}-2" src="latex3.png"><A href="node1.html#label1"><SUP>1</SUP></A>. </P><P class="margin">Set Constraints</P><P> A basic set constraint approximates a set value <IMG alt="S" src="latex4.png"> in three different ways: </P><UL><LI><P>Constraining the lower bound by set <IMG alt="s" src="latex5.png">: <IMG alt="s
\subseteq S" src="latex6.png">. The lower bound contains all elements that are at least contained in the set value. </P></LI><LI><P>Constraining the upper bound by set <IMG alt="s" src="latex5.png">: <IMG alt="S
\subseteq s" src="latex7.png">. The upper bound contains all elements that are at most contained in the set value. </P></LI><LI><P>Constraining the cardinality of a set by a finite domain interval <IMG alt="\{n,\ldots,m\}" src="latex8.png">: <IMG alt="n \le \#S \le
m." src="latex9.png">. The cardinality constraint determines the minimal and maximal number of elements allowed to be contained in the set. </P></LI></UL><P> 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><P>Non-basic set constraints, as intersection <IMG alt="\cap" src="latex10.png">, union <IMG alt="\cup" src="latex11.png">, disjointness <IMG alt="\|" src="latex12.png">, and the like, are provided as propagators. For details on the provided set propagators see <A href="../system/node33.html#chapter.fs">Chapter 7 of ``System Modules''</A>. </P><P class="margin">Set Constraint Propagation</P><P> To explain constraint propagation, assume the basic set constraints:<IMG alt="\emptyset
\subseteq X,Y \subseteq \{1,\ldots,5\}" src="latex13.png"> and additionally the following non-basic constraints: <IMG alt="X \cup Y =
\{1,\ldots,5\}" src="latex14.png"> and <IMG alt="X \| Y" src="latex15.png">. Adding the constraints <IMG alt="1 \in X" src="latex16.png"> and <IMG alt="2 \notin Y" src="latex17.png"> yields the intermediate store <IMG alt="\{1\} \subseteq X \subseteq
\{1,\ldots,5\}" src="latex18.png"> and <IMG alt="\emptyset \subseteq Y \subseteq
\{1,3,4,5\}" src="latex19.png">. The present non-basic constraints can add even more basic constraints: the disjointness constraint removes 1 from the upper bound of <IMG alt="Y" src="latex20.png"> since 1 was added to the lower bound of <IMG alt="X" src="latex21.png">. The union constraint adds 2 to the lower bound of <IMG alt="X" src="latex21.png"> since 2 was removed form the upper bound of <IMG alt="Y" src="latex20.png">. After that, propagation has reached a fixed-point and leads to <IMG alt="\{1,2\} \subseteq X \subseteq \{1,\ldots,5\} \wedge
\emptyset \subseteq Y \subseteq \{3,4,5\}" src="latex22.png">. Bringing the cardinality constraint <IMG alt="3 \le \#Y \le 5" src="latex23.png"> into play determines <IMG alt="Y" src="latex20.png"> to <IMG alt="\{3,4,5\}" src="latex24.png"> 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 <IMG alt="X" src="latex21.png">'s upper bound and that way determines <IMG alt="X" src="latex21.png"> to <IMG alt="\{1,2\}" src="latex25.png">. </P><P class="margin">Connecting Finite Sets and Finite Domains</P><P> 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 <A href="../system/node33.html#chapter.fs">Chapter 7 of ``System Modules''</A> for details on <CODE>FS<SPAN class="keyword">.</SPAN>int<SPAN class="keyword">.</SPAN>min</CODE> resp. <CODE>FS<SPAN class="keyword">.</SPAN>int<SPAN class="keyword">.</SPAN>max</CODE>). Another possibility is to match the elements of a set of a certain cardinality <IMG alt="c" src="latex26.png"> with a tuple of <IMG alt="c" src="latex26.png"> finite domains (see <A href="../system/node33.html#chapter.fs">Chapter 7 of ``System Modules''</A> for details on <CODE>FS<SPAN class="keyword">.</SPAN>int<SPAN class="keyword">.</SPAN>match</CODE>) that is used in <A href="node2.html#fset.examples.steiner">Chapter 2</A>. </P><P class="margin">Distribution</P><P> 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 <IMG alt="n \in S \vee n \notin S" src="latex27.png">. The following figure illustrates that. </P><DIV align="center"><IMG alt="" src="setdistr.gif" id="setdistr.pic"></DIV><P> </P><P> </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="index.html">- Up -</A></TD><TD><A href="node2.html#fset.examples.steiner">Next >></A></TD></TR></TABLE><HR align="left" width="30%"><DIV class="footnote"><A name="label1">1. </A>The reason for this value is as follows: efficient integers (so-called <EM>small integers</EM> in Mozart Oz 3) occupy 28 bits. Hence the biggest positive integer is <IMG alt="2^{27}-1" src="latex28.png">. To be able to represent the cardinality of a set by a small integer, the biggest element of a set is determined to <IMG alt="2^{27}-2" src="latex29.png">.</DIV><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~tmueller/">Tobias Müller</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|