Subsumption and Unification

Feature structures are inherently partial in the information they provide. Based on the type inheritance ordering, we can order feature structures based on how much information they provide. This ordering is referred to as the subsumption ordering. The notion of subsumption, or information containment, can be used to define the notion of unification, or information combination. Unification conjoins the information in two feature structures into a single result if they are consistent and detects an inconsistency otherwise.

Subsumption

We define subsumption, saying that $F$ subsumes $G$, if and only if:

• the type of $F$ is more general than the type of $G$
• if a feature $f$ is defined in $F$ then $f$ is also defined in $G$ such that the value in $F$ subsumes the value in $G$
• if two paths are shared in $F$ then they are also shared in $G$

Consider the following examples of subsumption, where we let < stand for subsumption:

  agr         <  agr
  PERS first     PERS first
                 NUM plu

  sign                phrase                 
  SUBJ agr         <  SUBJ agr 
       PERS pers           PERS first
                           NUM plu

  sign                sign
  SUBJ agr            SUBJ [0] agr
       PERS first          PERS first
       NUM plu     <       NUM plu
  OBJ agr             OBJ [0]
      PERS first
      NUM plu

  false               false              [1] false
  ARG1 false       <  ARG1 [0] false  <  ARG1 [1]
       ARG1 false          ARG1 [0]

Note that the second of these subsumptions holds only if pers is a more general type than first, and sign is a more general type than phrase. It is also important to note that the feature structure consisting simply of the type bot will subsume every other structure, as the type bot is assumed to be more general than every other type.

Unification

[Reference Manual]
[Code]
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.^4.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 plu

  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.