6.9 Selection Constraints

The selection constraint is based on the intuitive notion of selecting the th element out of a sequence of values. We write it abstractly as follows:

$X=\TUP{Y_1,\ldots,Y_n}[I]$

The notation $\TUP{Y_1,\ldots,Y_n}[I]$ was chosen to be reminiscent of array access, i.e. subscripting. The declarative semantics is simply:

that is: is equated with the th variable in the sequence $\TUP{Y_1,\ldots,Y_n}$ . However, unlike functional selection which would block until is known and then select the appropriate element, the above is a constraint that affects both and . If X=Y_k is inconsistent, then is removed from the domain of . Conversely, the information about can be improved by lifting the information common to all Y_i at positions that are still in the domain of . We will explain this in more detail later.

The idea of the selection constraint was first introduced by [DVS⁺88], but the sequence was restricted to integer values. In [Duc99a], I introduced a more general form that accepts homogeneous sequences of either FD variables or FS variables and has a very efficient implementation.

Of particular interest to the linguist is the fact that the selection constraint can express covariant assignments:

$\begin{array}{r@{{}={}}l} X&\TUP{X_1,\ldots,X_n}[I]\\ Y&\TUP{Y_1,\ldots,Y_n}[I] \end{array}$

These two selection constraints share the same selector and can be regarded as realizing the dependent (or named) disjunctions shown below ([MK89], [DE90], [Ger91], [Gri90]) both labeled with name :

$\begin{array}{l@{\quad\vee\ldots\vee\quad}l} (X=X_1 & X=X_n)_I\\ (Y=Y_1 & Y=Y_n)_I \end{array}$

Notational variants of dependent disjunctions have been used to concisely express covariant assignment of values to different features in feature structures. The selection constraint provides the same elegance, but additionally affords the benefits of efficient and effective constraint propagation.

6.9.1 Select Package

6.9.2 FD Selection Constraint

6.9.3 FS Selection Constraint

6.9.4 FS Selection Union Constraint