Tree Adjoining Grammar

The rules in a TAG (known as ''auxiliary trees'') are trees with a special leaf node known as the ''foot node''. The root (top) node and foot node must be labeled with the same symbol.

A TAG derivation starts with an ''initial tree'' (analogous to the start symbol in a Context-free Grammar ). Rewriting is accomplished via ''adjunction'', where an auxiliary tree is ''adjoined'' at a node (typically a non-leaf node) in the current tree. The root/foot label of the auxiliary tree must match the label of the node at which it adjoins. This operation splits the node which is the target of adjunction into a top half and bottom half; the top half is attached to the root of the adjoining tree whilst the bottom half is attached at the foot node of the adjoining tree.

This is the most basic variant of TAG; the most common variant adds another rewriting operation called ''substitution'', and other variants allow multi-component trees, trees with multiple foot nodes, and other extensions.

Tree-adjoining grammars are often described as "mildly context-sensitive", meaning that they possess certain properties that make them more powerful (in terms of Weak Generative Capacity ) than context-free grammars, but less powerful than context-sensitive grammars as defined in the Chomsky Hierarchy . Mildly context-sensitive grammars are (it is sometimes conjectured) powerful enough to model the grammars of Natural Language s while remaining efficiently Parseable in the general case.

EXTERNAL LINKS

The XTAG project , which uses a TAG for natural language processing.

Information About

Tree Adjoining Grammar