15.4 Finite Set Constraints

Finite set constraints are also known from constraint programming but much less popular than finite domain constraints. Nevertheless, it turns out that finite set constraints are extremely useful for natural language processing.

A finite set (FS) variable denotes a finite set of integers. A finite set constraint describes the values of finite set variables based on the usual set operations. The reader should carefully note the difference between finite domain (FD) variables and finite set variables. An FD-variable denotes a single integer which can be desribed by a finite set of possibilities. A FS-variable denotes a finite set of integers which may be empty or contain more than one element.

There is two forms of basic finite set constraint which can be entered directely into the Oz-constraint-store. The upper:

X={FS.var.upperBound 1#6} X={FS.var.lowerBound 2#4}

The former constraint states an upper bound $X\subseteq \{1,2,3,4,5,6\}$ whereas the latter requires a lower bound $\{2,3,4\}\subseteq X$ . Beside of basic set constraints there are the following set propagators:

{FS.subset X Y} X={FS.union Y Z} X={FS.partition [U V W]} {FS.include I X}

The declarative semantics of these constraints are rather obvious:

$\begin{array}{l} X \subseteq Y \\ X = Y \cup Z \\ X = U \uplus V \uplus W \\ I \in X \end{array}$

Operationally, set propagators increase upper bounds and decrease lower bounds of set variables in the constraint store. The propagation behaviour can be tested at the following example:

declare X={FS.var.upperBound 1#6} Y={FS.var.upperBound 1#2} Z={FS.var.upperBound 2#3} {FS.subset X {FS.union Y Z}} {FS.subset Y Z} {FS.include 2 Y} {Browse [X Y Z]}

There are more important set constraints in Oz that we will not present in this reader. Note also that we do not need distributors for set constraints.