Tree-adjoining grammar

Tree-adjoining grammar is defined by a finite set of elementary trees, which are either initial trees or auxiliary trees. Initial trees have root and internal nodes labeled with nonterminal symbols, and leaves labeled with terminals or nonterminals; auxiliary trees have a distinguished leaf called the foot node, labeled with the same nonterminal as the root. The operation of substitution replaces a nonterminal leaf with an initial tree whose root matches that nonterminal. The operation of adjunction inserts an auxiliary tree into an internal node of another tree, splitting the node and attaching the auxiliary tree's root and foot appropriately. These operations allow the derivation of derived trees, which represent the syntactic structure of a sentence. The set of strings yielded by the derived trees constitutes the language generated by the TAG.

TAGs are particularly suited for describing the syntax of natural languages because they can capture long-distance dependencies and cross-serial constructions that are problematic for context-free grammars. For example, in Dutch and Swiss German, subordinate clauses exhibit cross-serial dependencies between verbs and their objects, which TAGs can model using adjunction. TAGs also provide a natural account of raising and control constructions, where a single noun phrase appears to be the subject of multiple verbs. In computational linguistics, TAGs have been used to build wide-coverage grammars for English, such as the XTAG grammar, and for other languages, and they serve as the basis for several statistical parsers. The formalism has also been extended to synchronous TAGs for machine translation, where two TAGs are paired to model correspondences between source and target languages.

Tree-adjoining grammars generate a class of languages known as mildly context-sensitive languages, which are properly contained in context-sensitive languages and properly contain context-free languages. This class includes languages such as {a^n b^n c^n d^n} and the copy language {ww}, which are not context-free. The membership problem for TAGs is decidable in polynomial time; the standard parsing algorithm, based on dynamic programming, runs in O(n^6) time, where n is the length of the input string. This complexity is higher than the O(n^3) for context-free grammars but still practical for many natural language processing tasks. TAGs are also equivalent to linear indexed grammars and to combinatory categorial grammars in generative capacity, though the formalisms differ in their linguistic expressiveness.

Beyond its use in syntax, TAG has been applied to other domains such as music theory, where it models hierarchical structure in musical scores, and to bioinformatics for RNA secondary structure prediction. The concept of 'tree-local' multicomponent TAG (MCTAG) extends TAG by allowing sets of trees to be adjoined together, increasing generative power while maintaining polynomial parsing. A notable historical detail is that the idea of adjunction was inspired by the linguistic phenomenon of 'discontinuous constituents' observed in German and Dutch. The XTAG grammar project at the University of Pennsylvania, initiated in the late 1980s, was one of the first large-scale efforts to build a comprehensive TAG for English, and it influenced subsequent grammar development. TAG has also been used in psycholinguistics to model sentence processing, particularly the incremental construction of syntactic structure.

Elementary tree

A basic tree in TAG that is either an initial tree or an auxiliary tree.

Substitution

An operation that replaces a nonterminal leaf with an initial tree.

Adjunction

An operation that inserts an auxiliary tree into an internal node of another tree.

Foot node

The distinguished leaf of an auxiliary tree that has the same label as the root.

Mildly context-sensitive

A class of formal languages that are more powerful than context-free but less powerful than context-sensitive.