4.2 Dominance Constraints

We now present a formal language with which we can write tree descriptions. This is the language of Dominance Constraints with Set Operators as described in [DN00]. It has the following abstract syntax:

\phi\quad{:}{:}{=}\quad x\mathbin{R} y\ \mid\ 
x:f(x_1 \ldots x_n) \ \mid\ \phi\wedge\phi'

where variables x,y denote nodes and R\subseteq\{\EQ,\LT,\GT,\DJ\}. \LT represents proper dominance and \DJ disjointness. The constraint x\mathbin{R} y is satisfied when the relationship that holds between x and y is one in R. Thus x\mathbin{\{\EQ,\DJ\}}y is satisfied either when x and y are equal, or when they denote nodes in disjoint subtrees. We write x\LE y instead of x\mathbin{\{\EQ,\LT\}}y and generally omit braces when we can write a single symbol.

Consider again the scope ambiguity example:

It can be expressed as the following dominance constraint:

\begin{array}{ll}
&x_0:\textsf{forall}(x_1,x_2)\\
\wedge&y_0:\textsf{exists}(y_1,y_2)\\
\wedge&x_1:\textsf{yogi}\wedge x_2\LE z\\
\wedge&y_1:\textsf{guru}\wedge y_2\LE z\\
\wedge&z:\textsf{has}
\end{array}



Denys Duchier
Version 1.2.0 (20010221)