Representing auxiliary and initial trees

In order to use the head-driven parser for TAG I describe how trees are encoded in $\cal {R}$($\cal {L}$), and how a given TAG is represented by a set of definite clauses. I then describe how this set of clauses is divided in chain- and non-chain-rules.

Trees are represented by feature structures with attributes node, mrk, ds and term where the value of node represents the node label, mrk is a marker of which the role will be explained below, and ds is a list of daughter trees (in case of non-terminal nodes) or a list of words (in case of terminal nodes). The attribute term takes values yes,no depending on whether the node is terminal or not. Without loss of generality I furthermore assume that node labels consist of a feature structure with three attributes cat,bot and top of which the values are resp. the category label, the bottom features and the top features. Thus, the following tree:

is represented as a feature structure as follows (note that in this example no constraints are defined, hence the values of the attributes bot and top are unspecified)

$$\avm{\mbox{\it node}: \avm{\mbox{\it cat}:\mbox{\rm s}}\\ ... ... \langle \mbox{\rm left} \rangle } \rangle } \rangle }$$
This data structure is chosen to implement the idea that at least some information between bottom and top parts of labels is shared; this part is represented as the value of the cat attribute. This is useful to provide an appropriate definition for the `head' relation for TAG. This definition reads

If we were to write a TAG grammar, as a grammar of $\cal {R}$($\cal {L}$), then an initial tree Tree with substitution nodes D₁...D_n were to be defined as:

$$\mbox{\it sign}(\mbox{\rm Tree}) \mbox{\tt :-} sign(\mbox{\rm D}_{1}), \dots sign(\mbox{\rm D}_{n}), \phi.$$
An auxiliary tree Tree, with foot node Foot and substitution nodes D₁...D_n, on the other hand, were to be written as:

$$\mbox{\it sign}(\mbox{\rm M}) \mbox{\tt :-} \mbox{\it sign}(... ...{\rm Tree},\mbox{\rm Aux},\mbox{\rm Foot},\mbox{\rm M}), \phi.$$

However, for the meta-interpreter, we will not assume this representation, but assume that an initial tree is represented as a clause

where Tree is the partially instantiated initial tree; SubsNodes is a list of the un-instantiated substitution nodes in Tree, and Words are the words dominated by this initial tree. An auxiliary tree Aux with foot node Foot, substitution nodes SubsNodes and words Words is represented as

The basic idea will be that an initial tree corresponds to a non-chain-rule. The `daughters' of such a rule correspond to the substitution nodes of that initial tree. An auxiliary tree, on the other hand, corresponds to a chain-rule. The head of the rule will be the tree in which the auxiliary is adjoined; the mother of the rule will be the result of the adjunction. The other daughters of the rule will correspond to the substitution nodes of the auxiliary tree. The important part of this definition is the introduction, at the end of the list of daughters, of the relation `adjoin' which will be explained below. The following definitions of the predicates $\mbox{\it predict\_ncr}$ and $\mbox{\it select\_cr}$ are obtained. Note that the use of the fourth argument of the latter predicate will become clear later.