A Limitation of FUGs: No Structure over the Set of Values

To formally define a grammar, we define L as a set of labels or attribute names and C as a set of constants, or simple atomic values. A string of labels (that is an element of L^* is a path, and is noted { l₁...l_n}. A grammar defines a domain of admissible paths, D contained in L^*. D defines the skeleton of well-formed FDs.

In functional unification, the set of constants C has no structure. It is a flat collection of symbols with no relations between each other. All constraints among symbols must be expressed in the grammar. In linguistics, however, grammars assume a rich structure between properties: some groups of features are mutually exclusive; some features are only defined in the context of other features.

          
                 | Question
                 | Personal
     | Pronoun -|
     |           | Demonstrative
     |           | Quantified
Noun |
     | Proper
     |           | Count
     | Common --|
                 | Mass
          
          

Let's consider a fragment of grammar describing noun-phrases (NPs) using the systemic notation given in [#!Winograd83!#]. Systemic networks, such as this one, encode the choices that need to be made to produce a complex linguistic entity. They indicate how features can be combined or whether features are inconsistent with other combinations. The configuration illustrated by this fragment is typical, and occurs very often in grammars. The schema indicates that a noun can be either a pronoun, a proper noun or a common noun. Note that these three features are mutually exclusive. Note also that the choice between the features {question, personal, demonstrative, quantified} is relevant only when the feature pronoun is selected. This system therefore forbids combinations of the type {pronoun, proper} and {common, personal}.

The traditional technique for expressing these constraints in a FUG is to define a label for each non terminal symbol in the system. The resulting grammar is as follows:

          
((cat noun)
 (alt (((noun pronoun)
	(pronoun
	 ((alt (question personal demonstrative quantified)))))
       ((noun proper))
       ((noun common)
	(common ((alt (count mass))))))))
          
          

This grammar is, however, incorrect, as it allows combinations of the type ((noun proper) (pronoun question)) or even worse ((noun proper) (pronoun zouzou)). Because unification is similar to union of features sets, a feature (pronoun question) in the input would simply get added to the output. In order to enforce the correct constraints, it is therefore necessary to use the meta-FD NONE   (which prevents the addition of unwanted features) as shown below:

          
((alt (((noun pronoun)
	(common  NONE)
	(pronoun
	 ((alt (question personal demonstrative quantified)))))
       ((noun proper) (pronoun  NONE) (common  NONE))
       ((noun common)
	(pronoun  NONE)
	(common ((alt (count mass))))))))


The input FD describing a personal pronoun is then:
((cat noun)
 (noun pronoun)
 (pronoun personal))
          
          

There are two problems with this corrected FUG implementation. First, both the input FD describing a pronoun and the grammar are redundant and longer than needed. Second, the branches of the alternations in the grammar are interdependent: you need to know in the branch for pronouns that common nouns can be sub-categorized and what the other classes of nouns are. This interdependence prevents any modularity: if a branch is added to an alternation, all other branches need to be modified. It is also an inefficient mechanism as the number of pairs processed during unification is O(n^d) for a taxonomy of depth d with an average of n branches at each level.