Type Hierarchies

While feature structures are used to organize knowledge, types present ``an additional dimension along which to classify or organize knowledge'' [Penn2000]. In connection to feature structures, types can be seen as organizing feature structures into classes [Carpenter1992].

Types are organized into partially ordered sets, called type hierarchies. A complete definition of type hierarchies is given in [Carpenter1992] and [Penn2000]; in this section, only the definitions and theorems relevant to this thesis are presented.

Definition 2.1   A partial order on a set P is a relation $\le\ \subseteq P\times P$, such that $\forall x,y,z \in P:$

• $x\le x$ (reflexivity),
• if $x\le y$ and $y\le x$, then $x=y$ (anti-symmetry),
• if $x\le y$ and $y\le z$, then $x\le z$ (transitivity).

Definition 2.2   Given a partially ordered set $\langle P,\le\rangle$, the set of upper bounds of a subset $S\subseteq P$ is the set $S^u=\{y\in P\vert \forall x\in S, x\le y\}$.

Definition 2.3   A partially ordered set $\langle P,\le\rangle$ is bounded complete iff, $\forall S\subseteq P$ such that $S^u \neq \emptyset$, $S^u$ has a least element, called the least upper bound, or join, of $S$, written $\bigvee S$.

Definition 2.4   A type hierarchy is a non-empty, countable, bounded complete, partially ordered set.

For the particular case of interest to typed feature structures, three points must be noted. First, the order relation between types is subtyping ( $\sqsubseteq$), therefore a type hierarchy will be denoted as $\langle Type,\sqsubseteq\rangle$. Second, the least upper bound of a set S ($\bigvee S$) is written $\bigsqcup S$ (when S consists of only two elements $x$ and $y$, $\bigsqcup S = x \sqcup y$ - $x$ and $y$ are said to unify, and $\sqcup$ is the type unification operation). Finally, there is a special least element for non-empty bounded complete partial orders of types: $\bot$ (``bottom'' - the least type, or the most general type, which is more general than all other types in the hierarchy).