Variables in TFS Representations

A particular point of interest with regard to the representation of grammar rules is the use of variables. The unification and instantiation mechanisms in Prolog allow the use of variables to represent structure shared between daughters or between a daughter and the rule's mother. The example from Figure 3.2 is significant from this point of view: the features agr in the two daughters share the same structure, indicated by the variable Agr. Similarly, semantic information is shared between the mother and each of the two daughters through the variables VPSem and NPSem.

The use of variables to share structure is a powerful characteristic of TFSGs. This thesis introduces a new clasification of the instances of variables, based on what type of structure sharing they create: internal variables, active external variables, and inactive external variables. Over the next chapters, the importance of these variables for indexing will be revealed.

Internal variables:

the instances of these variables represent internal structure sharing. An example of such internal sharing can be found in the AVM from Figure 2.6 on page . The occurrences of the instances of such variables are limited to a single category in the grammar.

External Variables:

are instances of variables such as Agr, NPSem, and VPSem from Figure 3.2. They are used to share structure across categories (daughters). These instances can occur in the entire grammar rule. It is possible for a variable instance to be used for structure sharing both inside a category (as an internal variable) and across categories; in this case, it is considered an external variable. For a specific category, two kinds of external variables can be distinguished, depending on their sharing with other categories and the parsing control strategy:

Active External Variables:

are instances of variables that are shared between the description of a category $D$ and descriptions of daughters in the same rule with $D$ that are visited before $D$ when the rule is extended. For example, if rules are extended from left to right, then the Active External Variables for a daughter $D_i$ are those variable instances shared between $D_i$ and all daughters $D_j$ with $j<i$ (daughters to the left of $D_i$). Since the evaluation is left to right, a daughter sitting to the right of $D_i$ sharing a variable with $D_i$ cannot have that variable instantiated before $D_i$ (i.e., external variables get instantiated in $D_i$ because daughters at its left were unified with edges in the chart^3.2). For a mother, all its External Variables are Active External Variables.

Inactive External Variables:

are the External Variable instances that are not active.

For the rest of this thesis, unless otherwise specified, a daughter's External Variables will refer to its Active External Variables.

A particular variable can be active for a daughter $D_i$, but inactive for a daughter $D_j$ in the same rule. In Figure 3.2, Agr is an Active External Variable in the second daughter, but it is an Inactive External Variable in the first daughter.

When a description is mapped to a feature structure with MGSat, External Variables correspond to structure sharing between feature structures (``external sharing''), as exemplified in Figure 3.3.

Figure 3.3: Structure sharing between two typed feature structures (``external sharing'').

It should be mentioned that by external sharing, a description's MGSat can ``grow'' nodes. For the example presented in Figure 3.2 and Figure 3.3, if the first daughter is unified with an edge
$\left[\begin{array}{l} \textrm{SYN: \textbf{np}}\\ \textrm{AGR: } \left[\begi... ...third}}\\ \textrm{NUMBER: \textbf{sing}} \end{array}\right] \end{array}\right]$,
then the two extra nodes connected to node $q_2$ in this daughter will also be shared by the second daughter, as shown in Figure 3.4.

Figure 3.4: Structure sharing between two typed feature structures, after unification.

Structure sharing (especially external sharing) is an important aspect of typed feature structures. Its relevance to parsing will be detailed in Chapter 6; but before closing this section, some extra notation is provided:

Definition 3.1   If $D_1,\dots, D_n$ are daughter descriptions in a rule, then $Ext(MGSat(D_i))$ is the set of nodes shared between $MGSat(D_i)$ and the daughters to its left in the same rule: $Ext(MGSat(D_i))=\underset{1\leq j < i}{\bigcap}Q_j$, where $Q_j$ is $MGSat(D_j)$'s set of nodes.

For a mother description $M$, $Ext(MGSat(M))$ is the set of nodes $q\in Q_M$ shared with any daughter in the same rule: $Ext(MGSat(M))=\underset{1\leq j \leq n}{\bigcap}Q_j$, where $n$ is the number of daughters in the rule, $Q_j$ is $MGSat(D_j)$'s set of nodes, and $Q_M$ is $MGSat(M)$'s set of nodes.

For the result of the unification between $M$ and $D$, $Ext(MGSat(M)\sqcup MGSat(D))=\{[x]_{\bowtie}\in Q_{M\sqcup D} \vert \exists y\in [x]_{\bowtie} \textrm{ such that } y\in Ext(MGSat(M))\cup Ext(MGSat(D)) \}$.

It should be mentioned that $Ext(MGSat(M))\cup Ext(MGSat(D))$ needs to be defined since daughters are unified during parsing with mothers inserted as edges in the chart. It should also be noted that $Ext$ is defined for MGSats of daughter and mother descriptions. For the rest of the thesis, when not specified otherwise, a daughter $D$ (and a mother $M$) will denote the most general satisfier of a daughter description (and of a mother description).