+ Auxiliary Levels

As it is, the cdg library can only represent all-quantified unary and binary constraints. While the idea of allowing arbitrary constraints has been entertained for years, off and on, this would require largish changes to the constraint engine and might turn out to make a constraint grammar unacceptably inefficient.

Therefore, some legitimate syntactical constraints cannot be expressed directly as CDG constraints. The most important of these is existence, the condition that particular words (prepositions, finite verbs) must be accompanied by particular complement words to be grammatical. Even the very first definition of CDG (Maruyama 1990, not available electronically) proposed a method for circumventing this restriction:

• define two levels of representation, a syntactical and an auxiliary level

• write constraints which ensure that the syntactical argument relation is exactly mirrored on the auxiliary level

• write the existence constraint on the auxiliary level by simply postulating that the corresponding edge there must not be NIL.

This is how the trick works in our constraint language:

// define two levels
SYN # SUBJ, OBJ, ROOT;
SYN_SUBJ # LINK;

// coupling
{X:SYN, Y:SYN_SUBJ} : syn_subj_map : syn_subj : 0.0 :
  X%AT%id=Y^id <-> X.label=SUBJ & X^id=Y%AT%id;

// existence
{X:SYN_SUBJ} : missing_subject : 0.001 :
  X%AT%cat = finite_verb
  ->
  ~root(X^id);

It has been extensively used to model existence, and we reported on it in our paper on grammar modelling.

However, using this trick is a considerable burden on the grammar. It requires multiple auxiliary levels to be defined (because one word may take more than one complement) which have no relation at all to the kind of representational level that a linguist would postulate. It has proven impossible to explain the purpose and working of these levels to any interested outsider. Finally, it is not particularly efficient itself because it multiplies the number of variables in a given problem by the number of auxiliary levels. Although most of the new variables are trivially solved, others introduce artificial (meaningless) hard constraint failures whenever a transformation step establishes or removes a complement, effectively doubling the number of transformation steps to get anything done.

The obvious idea is to have the parser treat these `mirror' edges specially, automatically adjusting them whenever a complement binding comes or goes. Apart from the fact that this is not a well-defined operation (if a temporary solutions posits two subjects for one word, where should the mirror edge go?), and that it would require changes to each of the solution methods, as well as to the input language, it has proven impractical; in practice, the coupling constraints are not without exceptions (think about coordinated phrases), so the task of maintaining them correctly is far too complicated to be done to the program - it can only be done by the grammar writer.

The current trend is therefore to get rid of artificial levels and instead bestow upon the constraint language exactly those powers that it needs. New predicates have been introduced that transcend the restriction to binary constraints in a controlled way. Extensive experimenting has established that using them is at least as efficient as using auxiliary levels while making the grammar much more understandable.

Here are two prime examples of such predicates:

• the predicate has() checks whether the word specified is modified by at least one other word with the given label. Here is how to write the subject existence constraint from above:

     {X:SYN} : missing_subject : 0.001 :
       X%AT%cat = finite_verb
       ->
       has(X%AT%id, SUBJ);
     

• the predicate is() checks whether the word specified itself modifies another word with the given label. Here is how to postulate the German `vorfeld' condition (a main clause has only one constituent to the left of the verb):

     {X/SYN/\Y/SYN} : Vorfeld : 0.1 :
       X^cat = finite_verb
       ->
       ~is(X^id,ROOT)
     

This also used to require an auxiliary level.

Note that each of these predicates checks features at least one edge that the constraint does not name explicitly. It is therefore not possible to apply a constraint which uses them to the two edges in isolation; instead the entire syntax structure must be available for investigation. This means that the constraints are not binary in the strict sense, but formally restrict all edges in the analysis simultaneously.

The reason why this does not lead to an explosion of effort is that they are still accessed like unary or binary constraints. The first example constraint performs an expensive search via has(), but only on words that are actually finite verbs. The second example constraint above is triggered by a particular configuration of two edges, and when called, it performs a single check on one further edge (the one above X and Y). Therefore it is almost as cheap as a normal binary constraint (a general ternary constraint would be called up to n³ times, while this is called at most n² times on a structure with n edges). The more expensive evaluation of the constraint formula is therefore kept in check by assuring that it is only done when actually needed (the cdg library guarantees that the logical operators in constraint formulas are short-circuited whenever possible).

Constraints like this could be called context-sensitive if the expression were not so firmly entrenched to mean something quite different. Their disadvantage is that they cannot be applied if the entire context is not available - that is, during propagation or normal search. The best such a solution method can do is to disregard these constraints while working and apply them retroactively on any complete structure that it may find. Although the constraints still help decide between complete structures, they are not available to guide the search toward the correct ones. Therefore, having many of these constraints in a grammar renders the netsearch method less efficient.

More serious is another objection: they are also unavailable during incremental processing. Note, however, that it is unclear whether we would want them available for incremental analysis. As long as the complement of a word is not available in the input, should we assign a penalty for the missing word or not? The probable answer is that we should not penalize the lack, but turn it into an expectation about the future, similar to the NONSPEC mechanism. This feature is only concerned with where to attach a word before its parent is available; existence constraints also make it necessary to think about where to satisfy one's valences before one's children are available. Therefore, incremental analysis does need to be changed to accommodate these more powerful constraints.