### 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 and . The strict yield of is the set of all descendents of that can be reached by traversing 1 or more dependency edges. The yield of is obtained by adding to its strict yield. In order to enforce acyclicity, we must require that does not occur in its strict yield. Therefore it suffices to define the yield of as being partitioned by 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 are finite set variables. Its declarative semantics are:

i.e. from the sequence , the sets occurring at all positions indicated by 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 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)