5.4.6 Yield and Acyclicity

The yield of a node is the set of nodes reachable through the transitive closure of complement and modifier edges, i.e. by traversing 0 or more dependency edges. We distinguish between yield and strict yield and introduce the corresponding variables \Feature{yield}(w) and \Feature{yieldS}(w). The strict yield of w is the set of all descendents of w that can be reached by traversing 1 or more dependency edges. The yield of w is obtained by adding w to its strict yield. In order to enforce acyclicity, we must require that w does not occur in its strict yield. Therefore it suffices to define the yield of w as being partitioned by \{w\} and its strict yield:


It remains to define the strict yield. For this purpose, we introduce a new member of the family of selection constraints: the selection union constraint:


where all of S,S_i,\textit{SI} are finite set variables. Its declarative semantics are:


i.e. from the sequence \TUP{S_1,\ldots,S_n}, the sets occurring at all positions indicated by \textit{SI} are selected and their union is returned. See also Section 6.9.4 for further discussion of the selection union constraint.

The strict yield of w is simply the union of the yields of its daughters:


The use of the selection union constraint improves and simplifies the formulation in [Duc99a].

Denys Duchier
Version 1.2.0 (20010221)