previous up contents next
Left: Inference in DATR Up: Formal theory of inference Right: Global inheritance

Local inheritance

  As a point of departure, this section provides rules of inference for a restricted variant of DATR which lacks both global inheritance and the default mechanism. This variant will be referred to as ${\tt DATR}_L$. The syntax of ${\tt DATR}_L$ is as given in Section 3.1.4 except, of course, that the three forms of global inheritance descriptor are omitted. An example of a simple ${\tt DATR}_L$ theory is presented below:

        <cat> == noun
        <suff> == s.
        <cat> == NOUN
        <root> == llama
        <sing> == <root>
        <plur> == <root> NOUN:<suff>.

The ${\tt DATR}_L$ theory defines the properties of two nodes, NOUN and Llama. The definitional sentences specify values for node/path pairs, where the specification is either direct (a particular value is exhibited), or indirect (the value is obtained by local inheritance). For example, the value of the node/path pair NOUN:<cat> is specified directly as noun. In contrast, the node/path pair Llama:<cat> obtains its value indirectly, by local inheritance from the value of NOUN:<cat>. Thus Llama:<cat> also has the value noun. The value of Llama:<plur> is specified indirectly by a sequence of descriptors Llama:<root> NOUN:<suff>. Intuitively, the required value is obtained by concatenating the values of the descriptors Llama:<root> and NOUN:<suff>, yielding llama s.

We wish to provide an inductive definition of an evaluation relation (denoted $\Longrightarrow$) between sequences of DATR descriptors in $\mbox{\sc desc}^*$ and sequences of atoms (i.e., values) in $\mbox{\sc atom}^*$. We write


to mean that the sequences of descriptors $\phi$ evaluates to the sequence of atoms $\alpha$. With respect to the ${\tt DATR}_L$ theory above we should expect that ${\tt \mbox {\tt Llama}\!:\!{\tt <cat\gt}}
\Longrightarrow\mbox{\tt noun}$ and that ${\tt \mbox {\tt Llama}\!:\!{\tt <root\gt}} \:\:
{\tt \mbox {\tt NOUN}\!:\!{\tt <suff\gt}} \Longrightarrow\mbox{\tt llama s}$, amongst other things.

Figure 3: Evaluation semantics for DATR$\mbox{}_L$
\mbox{\em Values\/...
 ...:{\tt <\alpha\gt}\Longrightarrow\beta} \end{array}\end{displaymath}}\end{figure}

The formal definition of $\Longrightarrow$ for ${\tt DATR}_L$ is provided by just four rules of inference, as shown in Figure 3. The rule for Values states simply that a sequence of atoms evaluates to itself. Another way of thinking about this is that atom sequences are basic, and thus cannot be evaluated further. The rule for Definitions was briefly discussed in the previous section. It permits inferences to be made about the values associated with node/path pairs, provided that the theory T contains the appropriate definitional sentences. The third rule deals with the evaluation of sequences of descriptors, by breaking them up into shorter sequences. Given that the values of the sequences $\phi$ and $\psi$ are known, then the value of $\phi\psi$ can be obtained simply by concatenation. Note that this rule introduces some non-determinism, since in general there is more than one way to break up a sequence of value descriptors. However, whichever way the sequence is broken up, the result (i.e., value obtained) should be the same. The following proof serves to illustrate the use of the rules Val, Def and Seq. It establishes formally that the node/path pair Llama:<plur> does indeed evaluate to llama s given the ${\tt DATR}_L$ theory above.

\infer[\mbox{\em Def\/}]{{\tt \mbox {\tt Llama}\!:\!{\tt <pl...
 ...{\em Val\/}]{\mbox{\tt s}\Longrightarrow\mbox{\tt s}}{}

The final rule of Figure 3 deals with DATR's evaluable path construct. Consider a value descriptor of the form $A\!:\; < B\!:\; < \gt \gt$. To determine the value of the descriptor it is first necessary to establish what path is specified by the path descriptor $<\:B\!:\; < \gt\gt$. This involves evaluating the descriptor $B\!:\; < \gt$ and then plugging in the resultant value $\alpha$ to obtain the path ${\tt <\alpha\gt}$. The required value is then obtained by evaluating $A\!:\; < \alpha \gt$. The rule for Evaluable Paths provides a general statement of this process: if a sequence of value descriptors $\phi$ evaluates to $\alpha$ and $N\!:\; < \alpha \gt$ evaluates to $\beta$, then $N\!:\; < \phi \gt$ also evaluates to $\beta$.


previous up contents next
Left: Inference in DATR Up: Formal theory of inference Right: Global inheritance
Copyright © Roger Evans, Gerald Gazdar & Bill Keller, Tuesday 10 November 1998