Unification

Unification is an operation defined over pairs of feature structures that combines the information contained in both of them if they are consistent and fails otherwise. In ALE, unification is very efficient.^3.3Declaratively, unifying two feature structures computes a result which is the most general feature structure subsumed by both input structures. But the operational definition is more enlightening, and can be given by simple conditions which tell us how to unify two structures. We begin by unifying the types of the structures in the type hierarchy. This is why we required the bounded completeness condition on our inheritance hierarchies; we want unification to produce a unique result. If the types are inconsistent, unification fails. If the types are consistent, the resulting type is the unification of the input types. Next, we recursively unify all of the feature values of the structures being unified which occur in both structures. If a feature only occurs in one structure, we copy it over into the result. This algorithm terminates because we only need to unify structures which are non-distinct and there are a finite number of nodes in any input structure.

Some examples of unification follow, where we use + to represent the operation:

  agr          +  agr      =  agr
  PERS first      NUM plu     PERS first
                              NUM sing

  sign              sign             sign
  SUBJ agr       +  SUBJ [0] bot  =  SUBJ [0] agr
       PERS 1st     OBJ [0]               PERS first
  OBJ agr                                 NUM plu
      NUM plu                        OBJ [0]

  t           t           t
  F [0] t  +  F t      =  F [1] t
  G [0]         F [1]       F [1]
              G [1]       G [1]

  agr         +  agr          =  *failure*
  PERS first     PERS second

  e_list  +  ne_list     =  *failure*
             HD a
             TL e_list

Note that the second example respects our assumption that the type bot is the most general type, and thus more general than agr. The second example illustrates what happens in a simple case of structure sharing: information is retrieved from both the SUBJ and OBJ and shared in the result. The third example shows how two structures without cycles can be unified to produce a structure with a cycle. Just as the feature structure bot subsumes every other structure, it is also the identity with respect to unification; unifying the feature structure consisting just of the type bot with any feature structure $F$ results simply in $F$. The last two unification attempts fail, assuming that the types first and second and the types e_list and ne_list are incompatible.