16.3.4 Long-Distance Dependencies

The model of subcategorization we have developed so far has two components. Each head word has a SUBCAT feature which contains a list of the complements it expects. Then phrasal rules like the VP rule in (16.15) match up each expected complement in the SUBCAT list with an actual constituent. This mechanism works fine when the complements of a verb are in fact to be found in the verb phrase.

Sometimes, however, a constituent subcategorized for by the verb is not locally instantiated, but stands in a long-distance relationship with its predicate. Here are some examples of such long-distance dependencies:

LONG-DISTANCE DEPENDENCIES

What cities does Continental service?

What flights do you have from Boston to Baltimore?

What time does that flight leave Atlanta?

In the first example, the constituent what cities is subcategorized for by the verb service, but because the sentence is an example of a wh-non-subject-question, the object is located at the front of the sentence. Recall from Ch. 12 that a (simple) phrase-structure rule for a wh-non-subject-question is something like the following:

$$ S\ \to\ \mathrm{Wh-NP}\mathrm{Aux}\mathrm{NP}\mathrm{VP} $$

Now that we have features, we can augment this phrase-structure rule to require the Aux and the NP to agree (since the NP is the subject). But we also need some way to augment the rule to tell it that the Wh-NP should fill some subcategorization slot in the VP. The representation of such long-distance dependencies is a quite difficult problem, because the verb whose subcategorization requirement is being filled can be quite distant from the filler. In the following (made-up) sentence, for example, the wh-phrase which flight must fill the subcategorization requirements of the verb book, despite the fact that there are two other verbs (want and have) in between:

Which flight do you want me to have the travel agent book?

Many solutions to representing long-distance dependencies in unification grammars involve keeping a list, often called a gap list, implemented as a feature GAP, which is passed up from phrase to phrase in the parse tree. The filler (for example which flight above) is put on the gap list, and must eventually be unified with the subcategorization frame of some verb. See Sag and Wasow (1999) for an explanation of such a strategy, together with a discussion of the many other complications that must be modeled in long-distance dependencies.

16.4 IMPLEMENTING UNIFICATION

As discussed, the unification operator takes two feature structures as input and returns a single merged feature structure if successful, or a failure signal if the two inputs are not compatible. The input feature structures are represented as directed acyclic graphs (DAGs), where features are depicted as labels on directed edges, and feature values are either atomic symbols or DAGs. As we will see, the implementation of the operator is a relatively straightforward recursive graph matching algorithm, suitably tailored to accommodate the various requirements of unification. Roughly speaking, the algorithm loops through the features in one input and attempts to find a corresponding feature in the other. If all of the respective feature values match, then the unification is successful. If there is a mismatch then the unification fails. Not surprisingly, the recursion is motivated by the need to correctly match those features that have feature structures as their values.

A notable aspect of this algorithm is that rather than constructing a new feature structure with the unified information from the two arguments, it destructively alters the arguments so that in the end they point to exactly the same information. Thus, the result of a successful call to the unification operator consists of suitably altered versions of the arguments. As is discussed in the next section, the destructive nature of this algorithm necessitates certain minor extensions to the simple

graph version of feature structures as DAGs we have been assuming.