Parsing as Unification of MRSs

The benefit of regarding phrase rules as MRSs is reflected in the simplicity of defining the basic operation of parsing: rule completion. If a rule has $n$ daughters, and the rule is represented as an MRS $R=\langle D_1, \dots, D_n, M\rangle$ (where $D_1,\dots, D_n$ are MGSats of the rule's daughters and $M$ is the MGSat of the mother), then completing the rule is achieved by obtaining the sequence $R^{\widehat{1}}, \dots, R^{\widehat{n}}$, where each intermediate MRS $R^{\widehat{i}}$ represents the rule (the active edge) after $D_i$ is unified with an edge in the chart. The following paragraphs introduce a formal definition of the rule completion process.

Definition 4.1   If $F$ is a typed feature structure $\langle Q, \overline{q}, \theta, \delta\rangle$, then $\langle F,i,n\rangle$, the expansion of $F$ to position $i$ in a MRS of length $n$, is $\langle Q', \overline{Q}, \theta, \delta\rangle$, where:

• $Q' = Q \cup \overline{Q'}$, where $\overline{Q'}=\{\overline{q'_j} \vert 1\leq j\leq n, j\neq i, \theta(\overline{q'_j})=\bot\}$,
• $\overline{Q}=\{\overline{q_j} \vert 1\leq j \leq n\}$ is an ordered set such that $\overline{q_j}= \left\{\begin{array}{ll} \overline{q}, & \textrm{if } j=i \\ \overline{q'_j}, & \textrm{otherwise} \end{array}\right.$.

Definition 4.2   For a rule represented by a MRS $R=\langle D_1, \dots D_n, M \rangle$, its first active edge (after $D_1$ is unified with an edge $E_1$ from the chart) is an MRS $R^{\widehat{1}}= R \sqcup \langle E_1, 1, n\rangle$. Consequently, its $i$-th active edge (after $D_i$, $1 < i \leq n$, is unified with an edge $E_i$ from the chart) is an MRS $R^{\widehat{i}}= R^{\widehat{i-1}} \sqcup \langle E_i, i, n\rangle$.

If $R=\langle D_1, \dots D_n, M \rangle$ is an MRS representing a rule, and $R^{\widehat{i}}$ is its $i$-th active edge, then $R^{\widehat{i}}$ can be written as $\langle {D_1}^{\widehat{i}}, \dots {D_n}^{\widehat{i}}, M^{\widehat{i}} \rangle$. ${D_1}^{\widehat{i}}, \dots {D_n}^{\widehat{i}}$ represent $R$'s daughters (and $M^{\widehat{i}}$ its mother) after the first $i$ daughters are unified with edges in the chart. As underlined by Wintner wintner97thesis, the TFSs induced by a MRS are not (necessarily) independent, due to the nodes shared between them. The following definition introduces the relation (represented by the mapping operator $\mapsto$) between nodes in $R$ and $R^{\widehat{i}}$:

Definition 4.3   If $R^{\widehat{0}}=R=\langle Q, \overline{Q}, \theta, \delta\rangle$ is a MRS of length $n$ representing a rule and $R^{\widehat{i}}=\langle Q^{\widehat{i}}, \overline{Q}^{\widehat{i}}, \theta, \delta\rangle$ is its $i$-th active edge, then:

• $\forall j\in (1,\dots,n)$, $\overline{q_j} \mapsto \overline{q_j}^{\widehat{i}}$,
• $\forall x\in Q$, $\forall x^{\widehat{i}} \in Q^{\widehat{i}}$, $x\mapsto x^{\widehat{i}}$ iff $\exists f\in Feat, \exists q\in Q, \exists q^{\widehat{i}} \in Q^{\widehat{i}} . q\mapsto q^{\widehat{i}}$, such that $\delta(f,q)= x$ and $\delta(f,q^{\widehat{i}})= x^{\widehat{i}}$.

The mapping from nodes of $R^{\widehat{i}}$ to nodes of $R$ associates a node in $R^{\widehat{i}}$ with a set of nodes in $R$:

Definition 4.4   If $R=\langle Q, \overline{Q}, \theta, \delta \rangle$, $R^{\widehat{i}}=\langle Q^{\widehat{i}}, \overline{Q}^{\widehat{i}}, \theta, \delta\rangle$, and $x^{\widehat{i}} \in Q^{\widehat{i}}$, then the set of nodes mappable to $x^{\widehat{i}}$ is $[x^{\widehat{i}}]^{-1}$, the largest set $\{x\in Q \vert x\mapsto x^{\widehat{i}}\}$. The set of nodes mappable to a set of nodes ${Q^{\widehat{i}}}'\subseteq Q^{\widehat{i}}$ is $[{Q^{\widehat{i}}}']^{-1}$, the largest set $\{x\in Q \vert \exists {x^{\widehat{i}}}'\in {Q^{\widehat{i}}}' \textrm{ such that }x\mapsto {x^{\widehat{i}}}'\}$.

An important relation between $\mapsto$ and type subsumption exists:

Proposition 4.1   If $R^{\widehat{i}}=\langle Q^{\widehat{i}}, \overline{Q}^{\widehat{i}}, \theta, \delta\rangle$, $R^{\widehat{j}}=\langle Q^{\widehat{j}}, \overline{Q}^{\widehat{j}}, \theta, \delta\rangle$, where $0\leq i < j \leq \vert\overline{Q}\vert$, then $\forall x^{\widehat{i}} \in [x^{\widehat{j}}]^{-1}, \theta(x^{\widehat{i}}) \sqsubseteq \theta(x^{\widehat{j}})$.

Proof. It will be demonstrated first that $\forall i\in (1,\dots,n)$, where $n=\vert\overline{Q}\vert$, if $R^{\widehat{i-1}}=\langle Q^{\widehat{i-1}}, \overline{Q}^{\widehat{i-1}}, \theta, \delta\rangle$ and $R^{\widehat{i}}=\langle Q^{\widehat{i}}, \overline{Q}^{\widehat{i}}, \theta, \delta\rangle$, then $\forall x^{\widehat{i-1}} \in [x^{\widehat{i}}]^{-1}, \theta(x^{\widehat{i-1}}) \sqsubseteq \theta(x^{\widehat{i}})$.

$R^{\widehat{i}} = R^{\widehat{i-1}} \sqcup \langle E, i, n\rangle$ (where $E$ is a TFS representing an edge in the chart.) Since $x^{\widehat{i-1}} \mapsto x^{\widehat{i}}$, then $\exists\pi\in Path$, $\exists j \in (1,\dots,n)$, such that $\delta(\pi,\overline{q_j}^{\widehat{i-1}})=x^{\widehat{i-1}}$ and $\delta(\pi,\overline{q_j}^{\widehat{i}})=x^{\widehat{i}}$ (where $\overline{q_j}^{\widehat{i-1}}$ and $\overline{q_j}^{\widehat{i}}$ are roots of $R^{\widehat{i-1}}$ and $R^{\widehat{i}}$ respectively.) Therefore, according to Definition 3.4, $\overline{q_j}^{\widehat{i-1}} \bowtie \overline{q_j}^{\widehat{i}}$, and thus, $x^{\widehat{i-1}}\bowtie x^{\widehat{i}}$. But according to the same definition, $\forall q\in [x^{\widehat{i}}]_{\bowtie}, \theta(x^{\widehat{i}}) \sqsupseteq \theta(q)$. Hence, $\theta(x^{\widehat{i-1}}) \sqsubseteq \theta(x^{\widehat{i}})$.

Since both $\sqsubseteq$ and $\mapsto$ are transitive, the proposition holds for any $R^{\widehat{i}}$ and $R^{\widehat{j}}$, where $0 \leq i < j \leq n$. $\qedsymbol$