16.2.1 Dominance Constraints

We will consider the following language of tree descriptions based on dominance constraints:

$\begin{array}{rcl} \phi &::=& \phi \wedge \phi'\\ & \mid& X\gleich Y \\ & \mid& X{\not=} Y \\ & \mid& X \dom Y \\ & \mid& X \neg\dom Y\\ & \mid& X \Neq (Y_1,\ldots,Y_n) \end{array}$

This language is a variant of the dominance constraints defined in the second lecture. The differences are as follows:

$X \gleich Y$ expresses that and must denote the same node. It's an abbreviation of $X \dom Y \wedge Y \dom X$ .
$X \neg\dom Y$ expresses that must not dominate . This couldn't be expressed in the original language.
The new language doesn't contain lambda binding constraints. This is for simplicity of presentation; it's not difficult to add binding constraints to the implementation. Note that we can now speak just about trees, instead of lambda structures, as the models of dominance constraints.
Labeling constraints have been replaced by `daughterhood' constraints $X \Neq (Y_1,\ldots,Y_n)$ ; the difference is that daughterhood constraints don't specify the label of . This, too, is for simplicity, and labels could be (and have been) added easily to the implementation.