Unification

The unification of two typed feature structures is an operation that produces a feature structure that is their least upper bound, with respect to the subsumption ordering. Unification fails when the two feature structures provide inconsistent information.

Intuitively, unification is accomplished by first unifying the types of the root nodes of the two feature structures, and replacing them with the result of the type unification. By recursion, nodes that are values of identical features are then unified, and replaced with the result of the unification. Failure occurs when an inconsistency between nodes occurs (i.e., when two types can not unify).

In order to formally describe unification, the notion of alphabetic variants must be defined:

Definition 2.11   Two feature structures are alphabetic variants, $F\sim F'$, if $F\sqsubseteq F'$ and $F'\sqsubseteq F$.

Based on the definition of alphabetic variants, as well as on the properties of equivalence relations (transitive, reflexive, and symmetric), equivalence classes over a set $X$ ( $[x]_\equiv = \{y\in X \vert y\equiv x\}$), and the quotient set of a set $X$ modulo $\equiv$ ( $X/_\equiv = \{[x]_\equiv \vert x\in X\}$), Carpenter carpenter defines feature structure unification as:

Definition 2.12   Suppose $F, F'$ are feature structures such that $F\sim\langle Q,\overline{q},\theta,\delta\rangle$, $F'\sim\langle Q',\overline{q}',\theta',\delta'\rangle$, and $Q\cap Q'=\emptyset$. The equivalence relation $\bowtie$ on $Q\cup Q'$ is defined as:

• $\overline{q}\bowtie\overline{q}'$,
• if $\delta(f,q)$ and $\delta'(f,q')$ are defined, and $q\bowtie q'$, then $\delta(f,q)\bowtie\delta'(f,q')$.

The unification of $F$ and $F'$ is then defined as:

$F\sqcup F'=\langle(Q\cup Q') /_{\bowtie},[\overline{q}]_{\bowtie},\theta^{\bowtie},\delta^{\bowtie}\rangle$

where

$\theta^{\bowtie}([q]_{\bowtie})=\bigsqcup\{(\theta\cup\theta')(q') \vert q'\bowtie q\}$

and

$\delta^{\bowtie}(f,[q]_{\bowtie})=\left\{\begin{array}{ll} [(\delta\cup\delta'... ...m{ is defined}\\ \textrm{ undefined}, & \textrm{ otherwise} \end{array}\right.$

if all the joins in the definition of $\theta^{\bowtie}$ exist. $F\sqcup F'$ is undefined otherwise.

Computationally, unification has a complexity of the order of $O(ack^{-1}(n)\cdot n)$, where n is the size of the feature structure and $ack$ is the Ackermann's function. However, as it will be shown in Section 2.4.2, the extensions needed in many applications increase the cost of the unification.