Typed Feature Structure Definition

For a given type hierarchy $\langle Type,\sqsubseteq\rangle$, and a finite set of features $Feat$, a typed feature structure can be defined as a rooted graph, where arcs are labeled with feature names and nodes are being labeled with types (feature values) [Carpenter1992,Penn2000]:

Definition 2.5   A typed feature structure over Type and Feat is a tuple $F=\langle Q, \overline{q}, \theta, \delta\rangle$ where:

• $Q$ is a finite set of nodes,
• $\overline{q}\in Q$ is the root node,
• $\theta: Q \rightarrow Type$ is a total node typing function,
• $\delta: Feat\times Q\rightarrow Q$ is a partial feature value function

such that $\forall q\in Q$, $\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 feature value function can be extended to paths. A path is a sequence of features [Carpenter1992,Penn2000], and the feature value function $\delta$ applied to a path $\pi$ and a node $q$ gives the node reached by following $\pi$ from $q$.

Definition 2.6   Given the set of all features $Feat$, a path is a finite sequence of features, $\pi\in Feat^*$.

The set of all paths will be referred to as $Path$.

Definition 2.7   Given a typed feature structure $F=\langle Q, \overline{q}, \theta, \delta\rangle$, its (partial) path value function is $\delta': Feat^*\times Q \rightarrow Q$ such that:

• $\delta'(\epsilon,q) = q$,
• $\delta'(f\pi,q) = \delta'(\pi,\delta(f,q))$.

Definition 2.8   Given a typed feature structure $F=\langle Q, \overline{q}, \theta, \delta\rangle$, if $\delta(\pi,q)\downarrow$, then the restriction of $F$ to $\pi$ is $F@\pi=\langle Q', \overline{q'}, \theta', \delta'\rangle$ where:

• $\overline{q'}=\delta(\pi,\overline{q})$,
• $Q'=\{\delta(\pi',\overline{q'})\vert\pi'\in Path\}$,
• $\delta'(f,q)=\delta(f,q)$ if $q\in Q'$,
• $\theta'(q)=\theta(q)$ if $q\in Q'$.

Definition 2.9   In a typed feature structure with the root $\overline{q}$ and the feature value function $\delta$, the node $x$ is the ancestor of a node $x'$ iff $\exists \pi, \pi' \in Path$ such that $\delta(\pi,\overline{q})=x$ and $\delta(\pi',x)=x'$.