Headed TAGs

In many linguistic theories, a `head' of a construction plays an important role. For example, heads of a construction determine what other parts the construction may have. Furthermore, heads carry the features associated with the construction as a whole (such as case, agreement). The notion `head' plays an important role in grammatical theories as diverse as Government and Binding, (Xbar theory); Generalized Phrase Structure Grammar (the head-feature convention); and Head-driven Phrase Structure Grammar.

A headed TAG is a TAG in which each elementary tree is a headed tree. As an example of a headed TAG, consider figure 2. For each non-terminal node in a headed tree it is specified which daughter is the head of that tree. In the examples I use arrows to indicate the head-daughter of a local tree. The notion `head-corner' is defined as the reflexive and transitive closure of the head relation. For example, in $\alpha_{4}^{}$ the terminal symbol `saw' is a head-corner of the root node. Similarly, in $\beta_{1}^{}$, the foot node is a head-corner of the root node. In talking about `the' head-corner of a tree $\gamma$, I refer to the unique terminal t in $\gamma$ such that t is a head-corner of $\gamma$.

I define a parser for headed and lexicalized TAGs for which the following two constraints hold:

• the anchor of an initial tree $\alpha$ must be a head-corner of the root node of $\alpha$.
• the foot node of an auxiliary tree $\beta$ must be a head-corner of the root node of $\beta$.

Note that these requirements are satisfied in grammar H₁. Clearly, as I have not constrained the notion `head' in any way, any lexicalized TAG can be transformed into a headed TAG obeying this constraint.

The constraints reflect how I want to use headed TAGs in a head-corner parser. In this parser processing will proceed essentially in an anchor-driven way for initial trees, and in a foot-driven way for auxiliary trees. The notion `head' generalizes the two cases, and is also meaningful in order to define an order of proceesing for sub-trees of elementary trees that do not contain an anchor or a foot node.

The parser proceeds anchor-driven because we want to make use of the fact that elementary trees are lexicalized. The parser proceeds foot-driven in order to avoid a problem that otherwise occurs in bidirectional parsers (cf. discussion below).