Typed Feature Structure Cuts

In certain applications (as it will be the case for the indexing methods introduced in Chapter 6), it is useful to treat a subset of the nodes in a TFS in a similar manner as TFSs. In this thesis, the concept of TFS cuts is introduced in order to provide a TFS-like treatment to subset of nodes.

Definition 2.19   A cut of a typed feature structure $F=\langle Q, \overline{q}, \theta, \delta\rangle$ is a tuple $F^{\textrm{\Cutleft}}= \langle Q',\overline{Q'},\theta,\delta\rangle$ where:

• $Q' \subseteq Q$ ( $Q'\neq\emptyset$), a finite set of nodes,
• $\overline{Q'} = \{\langle x,\Pi(x) \rangle \vert x\in Q' \textrm{ and } \exists y\in Q\setminus Q', \exists f . \delta(f,y)=x\}$, where $\Pi(x)=\{\pi \vert \delta(\pi,\overline{q})=x\}$, the set of pseudo-roots of $F^{\textrm{\Cutleft}}$.

The definition for the unification of typed feature structures can now be extended to allow for the unification of a typed feature structure with a cut of a typed feature structure. An example of a unification between a TFS and a cut is presented in Figure 2.7.

Definition 2.20   Suppose $F, G$ are typed feature structures such that $F\sim\langle Q_F,\overline{q_F},\theta,\delta\rangle$, $G\sim\langle Q_G',\overline{q_G}',\theta',\delta'\rangle$, $Q_F\cap Q_G = \emptyset$, and $F^{\textrm{\Cutleft}}\sim \langle Q'_F,\overline{Q'_F},\theta,\delta\rangle$ is a cut of F. The equivalence relation $\blacktriangleright\!\!\blacktriangleleft$ on $Q'_F\cup Q_G$ is defined as the least equivalence relation such that:

1. if $\langle q_F,\Pi(q_F) \rangle \in \overline{Q'_F}$ and $q_G \in Q_G$, then $q_F \blacktriangleright\!\!\blacktriangleleft q_G$ iff $\exists \pi\in \Pi(q_F)$ such that $\delta'(\pi,\overline{q_G})=q_G$,
2. if $\delta(f,q_F)\downarrow$ and $\delta'(f,q_G)\downarrow$, and $q_F \blacktriangleright\!\!\blacktriangleleft q_G$, then $\delta(f,q_F) \blacktriangleright\!\!\blacktriangleleft \delta'(f,q_G)$.

Figure 2.7: The unification between a TFS and a cut TFS.

Proposition 2.1   Suppose $F, G$ are typed feature structures such that $F\sim\langle Q_F,\overline{q_F},\theta,\delta\rangle$, $G\sim\langle Q_G',\overline{q_G}',\theta',\delta'\rangle$, $Q_F\cap Q_G = \emptyset$, $F^{\textrm{\Cutleft}}\sim \langle Q'_F,\overline{Q'_F},\theta,\delta\rangle$ is a cut of F, $\bowtie$ is the equivalence relation between $F$ and $G$ (from the unification definition), and $\blacktriangleright\!\!\blacktriangleleft$ is the equivalence relation between $F^{\textrm{\Cutleft}}$ and $G$ (from Definition 2.20). If $x\in Q'_F, y\in Q_G$, then $x\blacktriangleright\!\!\blacktriangleleft y \Leftrightarrow x\bowtie y$.

Proof. (By induction on least distance from a pseudo-root to a node $x\in Q'_F$)

Part 1:

$x\blacktriangleright\!\!\blacktriangleleft y \textrm{\mbox{$=\!\!\!>$}}x\bowtie y$.

Base case:

$\langle x,\Pi\rangle \in \overline{Q'_F}$.
Since $x\blacktriangleright\!\!\blacktriangleleft y$, $\exists \pi\in \Pi$ such that $\delta'(\pi, \overline{q_G})=y$. By definition of , $\delta(\pi,\overline{q_F})=x$; and by definition of $\bowtie$, $\overline{q_F} \bowtie \overline{q_G}$. Thus, according to the definition extending $\delta$ to paths, and according to the Condition 2 from the definition of $\bowtie$: $\delta(\pi,\overline{q_F}) \bowtie \delta'(\pi,\overline{q_G})$. Therefore, $x\bowtie y$.

Induction:

Suppose $x'\in Q'_F$ and $y'\in Q_G$ such that $x'\blacktriangleright\!\!\blacktriangleleft y'$ and $x'\bowtie y'$. According to Condition 2 in Definition 2.20, if $\exists x=\delta(f,x')$ and $\exists y=\delta(f,y')$, then $x\blacktriangleright\!\!\blacktriangleleft y$. However, $x'\bowtie y'$, and according to the definition of $\bowtie$, if $\delta(f,x')\downarrow$ and $\delta(f,y')\downarrow$, then $\delta(f,x')\bowtie \delta(f,y')$. Therefore, $x\bowtie y$.

Part 2:

$x\blacktriangleright\!\!\blacktriangleleft y \textrm{\mbox{$<\!\!\!=$}}x\bowtie y$. Similarly to $x\blacktriangleright\!\!\blacktriangleleft y \textrm{\mbox{$=\!\!\!>$}}x\bowtie y$.

$\qedsymbol$