Spurious ambiguity

The way in which adjunction and substitution is defined in previous subsections give rise to spurious ambiguities. For example, given two auxiliary trees $\beta_{5}^{}$ and $\beta_{6}^{}$ and a derived tree $\gamma$, the parser derives the application of $\beta_{5}^{}$ and $\beta_{6}^{}$ to $\gamma$ twice, corresponding to the applications $\beta_{5}^{}$($\beta_{6}^{}$($\gamma$)) and $\beta_{6}^{}$($\beta_{5}^{}$($\gamma$)). But the results of these derivations are clearly completely identical.

As an example, consider the following case in which $\gamma$, $\beta_{5}^{}$ and $\beta_{6}^{}$ are as in figure 4.18.

Figure 4.18: A derived tree and two auxiliary trees.

The application $\beta_{5}^{}$($\beta_{6}^{}$($\gamma$)) gives rise to two possible derived trees, depending on which node with category n, is chosen for adjunction (see figure 4.19 for an illustration). Clearly, the application $\beta_{6}^{}$($\beta_{5}^{}$($\gamma$)) gives the same two results. The parser thus delivers four results, where only two results are desirable.

The first two trees respectively corresponds to $\beta_{6}^{}$($\gamma$) and $\beta_{5}^{}$($\gamma$). Depending on the adjunction node, these two trees both can be expanded in two ways, by the adjunction of the other auxiliary tree, resulting in two trees corresponding to $\beta_{5}^{}$($\beta_{6}^{}$($\gamma$)), and two trees corresponding to $\beta_{6}^{}$($\beta_{5}^{}$($\gamma$)). Four results are derived by the parser, where only two should be derived.

Figure 4.19: Illustration of spurious ambiguities.

Another spurious ambiguity arises when a tree is substituted in another tree, and afterwards adjunction in this tree is possible. The parser will prove two alternative derivations. The first derivation corresponds to the case in which the auxiliary tree is first adjoined in the derived tree, which then is substituted in the main tree. The second derivation corresponds to the case where the derived tree is substituted in the main tree; the auxiliary tree is afterwards adjoined (deep down) in this main tree.

It is straightforward to solve these problems by the following two principles. Firstly, once a tree is substituted in another tree this sub-tree is regarded `completed'. This means that no adjunctions take place in this tree. Similarly, if an auxiliary tree is adjoined at some node in a derived tree, then the sub-tree dominated by the foot node (in the result of the adjunction) is `completed' as well, and no further adjunctions under this foot node are possible. In the illustration I mark such `completed' sub-trees with the `#' marker.

The example given above is now derived only twice as follows. Firstly, the application $\beta_{6}^{}$($\gamma$) gives rise to a derived tree in which the embedded n node is marked completed. For that reason applying $\beta_{5}^{}$ to it only gives rise to one possibility, because the marker on the node n₁ prevents adjunction at n₁, and hence only adjunction at node n₂ is possible (see figure 4.20 for illustration). The derivation $\beta_{6}^{}$($\beta_{5}^{}$($\gamma$)) produces the other possibility.

Figure 4.20: Preventing spurious ambiguity.

In this way, trees are constructed in a bottom up fashion. Once you adjoin at a given node, then everything under (the bottom part) of this node is completed.

The prevention of spurious ambiguity is easily implemented using the attribute mrk in the data structure representing trees. The node in a tree representing a substitution node will be marked `completed'. Note that this marker remains after substitution. Similarly, the marker of a node representing a foot node will be marked `completed'. This changes the representation of initial and auxiliary trees. The adjunction predicate, furthermore, is defined in such a way that it may only penetrate nodes, which are not marked `completed'. Note that in the definition of adjoin this is already achieved.