Subsumption

Typed feature structure subsumption is an extension of the order relation between types. It defines a relation between feature structures that express the fact that one feature structure is more informative than the other. Formally, this is again defined in [Carpenter1992]:

Definition 2.10   For a type hierarchy $\langle Type,\sqsubseteq\rangle$ and a finite set of features $Feat$, a feature structure $F=\langle Q, \overline{q}, \theta, \delta\rangle$ subsumes a feature structure $F'=\langle Q', \overline{q}', \theta', \delta'\rangle$, $F\sqsubseteq F'$, iff there is a morphism $h:Q\rightarrow Q'$ such that:

• $h(\overline{q})=\overline{q}'$,
• $\forall q\in Q,$ $\theta(q) \sqsubseteq\theta'(h(q))$,
• $\forall f\in Feat, \forall q\in Q$, such that $\delta(f,q)$ is defined, $h(\delta(f,q))=\delta'(f,h(q))$.

Figure 2.4 illustrates an example of a subsumption relation between two feature structures [Carpenter1992], given a type hierarchy. An interesting observation is that, computationally, subsumption checking is not expensive, being computed in linear time of the size of the feature structure.

Figure 2.4: A subsumption example.

$\left[\begin{array}{l} \textrm{\textbf{sign}}\\ \textrm{AGR: } \left[\begin{... ...irst}}\\ \textrm{NUM: \textbf{singular}} \end{array}\right] \end{array}\right]$