TFS Grammar Rules

The previous section presented instances of variables in logical descriptions as the source for information sharing. In TFSG parser implementations however, the structure sharing is observed at the node level. This creates difficulties in formalizing the concept of structure sharing across most general satisfiers of daughters in the same rule.

Wintner wintner97thesis proposes a formal definition of phrase structure rules using feature structures. In this formalization, a rule is regarded as a feature structure with multiple roots, where each root corresponds to the root of the rule's mother and daughters. A version of the multi-rooted feature structures, adapted to the domain of this thesis, is given here.

Before formally introducing the phrase rule definition, several supporting definitions must be given.

Definition 3.2   A multi-rooted typed feature structure (MRS) over $Type$ and $Feat$ is a tuple $R=\langle Q, \overline{Q}, \theta, \delta \rangle$ where:

• Q is a finite set of nodes,
• $\overline{Q} \in Q$ is an ordered sequence of roots (possibly containing duplicates),
• $\theta: Q \rightarrow Type$ is a total node typing function,
• $\delta: Feat\times Q\rightarrow Q$ is a partial feature value function

such that for all $q\in Q$, there exists $\overline{q}\in \overline{Q}$ and there exists a finite sequence of features $f_1,\dots,f_n\in Feat$ that connects $\overline{q}$ to $q$ with $\delta$: $q=\delta(f_n,\dots\delta(f_2,\delta(f_1,\overline{q})))$. The length of a MRS is the number of its roots, $\vert\overline{Q}\vert$.

A MRS can be seen as an ordered sequence of feature structures $R=\langle F_1, \dots, F_n\rangle$ with shared nodes. If $\overline{q_i}$ is a root in $\overline{Q}$, then $F_i$ is the feature structure induced by the $i$-th root of $R$. $F_i$ contains all the nodes in $Q$ that are reachable from $\overline{q_i}$.

Definition 3.3   If $R=\langle Q, \overline{Q}, \theta, \delta \rangle$ is a MRS, then its induced feature structures are $F_1, \dots, F_n$ such that $\forall i\in (1,\dots,n)$, $F_i=\langle Q_i, \overline{q_i}, \theta, \delta \rangle$ where:

• $\overline{q_i}$ is the root node at position $i$ in $\overline{Q}$,
• $Q_i$ is the largest set of nodes $\{q\in Q\}$ such that $\exists \pi . \delta(\pi,\overline{q_i})=q$.

The unification of two MRSs can be defined as follows:

Definition 3.4   Suppose $R$ and $R'$ are multi-rooted feature structures of length $n$ such that $R=\langle Q, \overline{Q}, \theta, \delta \rangle$ and $R'=\langle Q', \overline{Q}', \theta', \delta' \rangle$. The equivalence relation $\bowtie$ on $Q\cup Q'$ is defined as:

• $\overline{q_i}\bowtie\overline{q_i}', \forall i \in (1,\dots,n)$,
• 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 $R$ and $R'$ is then defined as:

$R\sqcup R'=\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. $R\sqcup R'$ is undefined otherwise.

A phrase structure rule can now be seen as a MRS, where each constituent is a TFS in the MRS.

Definition 3.5   A phrase rule is a multi-rooted feature structure $R=\langle F_1, \dots, F_n\rangle$ of length $n>0$ with a distinguished last element. $F_n$ is the mother, while $F_1, \dots, F_{n-1}$ are the daughters: $F_1, \dots, F_{n-1} \textrm{\mbox{$=\!\!\!>$}}F_n$.

Figure 3.5 presents Wintner's example of a TFS rule seen as a MRS [Wintner1997]. The rule is written as $F_1, \dots, F_{n-1} \textrm{\mbox{$=\!\!\!>$}}F_n$ (being equivalent to a derivational rule: $F_n \rightarrow F_1, \dots, F_{n-1}$.)

Figure 3.5: A phrase rule seen as a MRS.

$$\left[\!\!\begin{array}{ll} \textrm{\textbf{phrase}} & \\ \textr... ...}}\\ \textrm{SUBJ:} & [1]\\ \textrm{HEAD:} & [2] \end{array}\!\!\right] \ \$$