Constraints

The formulas of the logic (constraints) are built from a set V of variables, a set C of constants and a set L of labels (also called attributes or features). Variables are thought of as referring to some specific feature structure. The labels are thought of as pointing to a specific part of a feature structure. A path will be a (possibly empty) sequence of such labels. Such a path can be viewed as the `address' of some piece of information in a specific feature structure. For example the path syn agr person will point to the person part of the agr part of the syn part.

A descriptor is a sequence sp where s is either a variable or a constant, and p is a (possibly empty) path. I write $\epsilon$ to refer to empty paths. Examples of descriptors are

$$\begin{array}{l} \mbox{\rm X}_{0} \mbox{\it l}_{1} \mbox{\it ... ... \mbox{\rm c} \mbox{\it l}_{1}\\ \mbox{\rm X}_{0} \end{array}$$
assuming that X₀ is a variable, l_i are labels and c is a constant. ^2.1

Atomic constraints (also called path equations) are equations of the form:

$$d_1 \doteq d_2$$
where d₁ and d₂ are descriptors. For example, the following expressions are atomic constraints, assuming that {X₁,X₂} $\subseteq$ V, {syn,agr,number} $\subseteq$ L and {singular} $\subseteq$ C:

$$\mbox{\rm X}_{1}~\mbox{\it syn}~\mbox{\it agr}~\mbox{\it number} \doteq \mbox{\rm singular}$$

$$\mbox{\rm X}_{1}~\mbox{\it syn}~\mbox{\it agr} \doteq \mbox{\rm X}_{2}~\mbox{\it syn}~\mbox{\it agr}$$
An $\cal {L}$-constraint is a set of such atomic constraints, i.e. a set of path equations. The equations in such a constraint are interpreted conjunctively. I write such a constraint as a sequence of equations separated by commas:

$$\phi_{1}^{}$$,...,$$\phi_{n}^{}$$

In the following, d is used to refer to descriptors in general, X_i refers to variables, l_i refers to labels, c_i refers to constants, s and t refer to either constants or variables and p and q refer to paths.