3 - Unification

Summary

The previous chapter presented four different views of feature structures, with several correspondences among them. For each of the views, a subsumption relation was defined in a natural way. In this chapter we define the operation of unification for the different views. The subsumption relation compares the information content of feature structures. Unification combines the information that is contained in two (compatible) feature structures.We use the term “unification” to refer to both the operation and its result. In the sequel, whenever two feature structures are related, they are assumed to be over the same signature.

The mathematical interpretation of “combining” two members of a partially ordered set is to take the least upper bound of the two operands with respect to the partial order; in our case, subsumption. Indeed, feature structure unification is exactly that. However, since subsumption is antisymmetric for feature structures and AFSs but not for feature graphs and AVMs, a unique least upper bound cannot be guaranteed for all four views. We begin with feature graphs and define unification for this view first, extending it to feature structures in Section 3.3. We then (Section 3.2) provide a constructive definition of feature graph unification and prove that it corresponds to the least upper bound definition in a naturalway. We also provide in Section 3.4 an algorithm for computing the unification of two feature graphs. AVM unification can then be defined indirectly, using the correspondence between feature graphs and AVMs. We define unification directly for AFSs in Section 3.5. We conclude this chapter with a discussion of generalization, a dual operation to unification.