Tree-Adjoining Grammars

Tree-Adjoining Grammars (TAGs) were introduced by Joshi et al. (1975) and developed extensively by Joshi and colleagues over the following decades (see Joshi and Schabes 1997 for a comprehensive overview). Where a context-free grammar builds structure by rewriting a single nonterminal at each step, a TAG takes trees as its primitive objects and combines them using two operations: substitution and adjunction.

The formalism

A TAG $G = \langle \Sigma, N, I, A, S \rangle$ consists of a terminal alphabet $\Sigma$, a nonterminal alphabet $N$, a finite set $I$ of initial trees (trees rooted in $S$ whose leaves are either terminals or nonterminals marked for substitution, notated $\downarrow$), a finite set $A$ of auxiliary trees (trees with exactly one distinguished leaf—the foot node—which carries the same label as the root), and a start symbol $S \in N$. The trees in $I \cup A$ are called elementary trees, and they represent the basic structural building blocks of the grammar, often corresponding to lexical items and their argument structures.

Substitution is the simpler of the two operations: if a derived tree has a leaf labeled $X\!\downarrow$ and an initial tree is rooted in $X$, we replace the leaf with that tree. This is directly analogous to applying a CFG rule $X \rightarrow \alpha$. Adjunction is what gives TAGs their extra power. If $\beta \in A$ is an auxiliary tree rooted in $X$ with a foot node also labeled $X$, and some derived tree $\gamma$ has an internal node labeled $X$, then we can adjoin $\beta$ at that node: we remove the subtree rooted at $X$ in $\gamma$, replace it with $\beta$, and attach the removed subtree at the foot node. The effect is that $\beta$ “wraps around” the original subtree, inserting material both above and below (or equivalently, to the left and right on the string) of whatever was there before. It is this wrapping that allows TAGs to generate non-context-free languages, because it lets us build up cross-serial dependencies incrementally.

To see how this works, recall the Swiss German cross-serial dependency pattern from the section on CFG limitations. In a TAG, each verb contributes an auxiliary tree that wraps its NP argument on one side and the verb itself on the other around the existing structure. Repeated adjunction of these auxiliary trees builds up the $\text{NP}_1 \text{NP}_2 \ldots \text{V}_1 \text{V}_2 \ldots$ pattern with the argument dependencies intact—something a CFG cannot do.

Equivalences and parsing

Vijay-Shanker and Weir (1994) proved that the string languages generated by TAGs are exactly the same as those generated by MCFGs with fan-out 1. (Fan-out is the number of string components a nonterminal can yield; we’ll define this precisely in the MCFG section.) This means TAGs sit at the bottom of the MCFG hierarchy: they are MCFGs where each nonterminal contributes exactly one contiguous string.

TAG parsing can be done in $O(n^6)$ time using a CKY-style algorithm, compared to $O(n^3)$ for CFGs. The increase in exponent comes from the adjunction operation, which requires tracking both the top and bottom of the adjoined tree. This is still polynomial—satisfying the MCS requirement of tractable parsing—and the deductive parsing framework extends naturally to TAGs: the items are more complex (they track both substitution and adjunction sites), but the agenda-based algorithm is the same.

The XTAG project developed a wide-coverage TAG grammar for English containing thousands of elementary trees organized by verb argument structure. It remains one of the most detailed formal grammars ever constructed for a natural language.

References

Joshi, Aravind K., Leon S. Levy, and Masako Takahashi. 1975. “Tree Adjunct Grammars.” Journal of Computer and System Sciences 10 (1): 136–63.

Joshi, Aravind K., and Yves Schabes. 1997. “Tree-Adjoining Grammars.” In Handbook of Formal Languages, vol. 3. Springer.

Vijay-Shanker, K., and David J. Weir. 1994. “The Equivalence of Four Extensions of Context-Free Grammars.” Mathematical Systems Theory 27 (6): 511–46.

--- title: Tree-Adjoining Grammars bibliography: ../../references.bib --- Tree-Adjoining Grammars (TAGs) were introduced by @joshi1975tree and developed extensively by Joshi and colleagues over the following decades [see @joshi1997introduction for a comprehensive overview]. Where a context-free grammar builds structure by rewriting a single nonterminal at each step, a TAG takes *trees* as its primitive objects and combines them using two operations: substitution and adjunction. ## The formalism A TAG $G = \langle \Sigma, N, I, A, S \rangle$ consists of a terminal alphabet $\Sigma$, a nonterminal alphabet $N$, a finite set $I$ of *initial trees* (trees rooted in $S$ whose leaves are either terminals or nonterminals marked for substitution, notated $\downarrow$), a finite set $A$ of *auxiliary trees* (trees with exactly one distinguished leaf—the *foot node*—which carries the same label as the root), and a start symbol $S \in N$. The trees in $I \cup A$ are called *elementary trees*, and they represent the basic structural building blocks of the grammar, often corresponding to lexical items and their argument structures. Substitution is the simpler of the two operations: if a derived tree has a leaf labeled $X\!\downarrow$ and an initial tree is rooted in $X$, we replace the leaf with that tree. This is directly analogous to applying a CFG rule $X \rightarrow \alpha$. Adjunction is what gives TAGs their extra power. If $\beta \in A$ is an auxiliary tree rooted in $X$ with a foot node also labeled $X$, and some derived tree $\gamma$ has an internal node labeled $X$, then we can *adjoin* $\beta$ at that node: we remove the subtree rooted at $X$ in $\gamma$, replace it with $\beta$, and attach the removed subtree at the foot node. The effect is that $\beta$ "wraps around" the original subtree, inserting material both above and below (or equivalently, to the left and right on the string) of whatever was there before. It is this wrapping that allows TAGs to generate non-context-free languages, because it lets us build up cross-serial dependencies incrementally. To see how this works, recall the Swiss German cross-serial dependency pattern from the [section on CFG limitations](../cfgs-for-syntax.qmd). In a TAG, each verb contributes an auxiliary tree that wraps its NP argument on one side and the verb itself on the other around the existing structure. Repeated adjunction of these auxiliary trees builds up the $\text{NP}_1 \text{NP}_2 \ldots \text{V}_1 \text{V}_2 \ldots$ pattern with the argument dependencies intact—something a CFG cannot do. ## Equivalences and parsing @vijayshanker1994equivalence proved that the string languages generated by TAGs are exactly the same as those generated by [MCFGs](mcfgs-and-lcfrs.qmd) with fan-out 1. (Fan-out is the number of string components a nonterminal can yield; we'll define this precisely in the [MCFG section](mcfgs-and-lcfrs.qmd).) This means TAGs sit at the bottom of the MCFG hierarchy: they are MCFGs where each nonterminal contributes exactly one contiguous string. TAG parsing can be done in $O(n^6)$ time using a CKY-style algorithm, compared to $O(n^3)$ for CFGs. The increase in exponent comes from the adjunction operation, which requires tracking both the top and bottom of the adjoined tree. This is still polynomial—satisfying the MCS requirement of tractable parsing—and the [deductive parsing framework](../deductive-parsing.qmd) extends naturally to TAGs: the items are more complex (they track both substitution and adjunction sites), but the agenda-based algorithm is the same. The XTAG project developed a wide-coverage TAG grammar for English containing thousands of elementary trees organized by verb argument structure. It remains one of the most detailed formal grammars ever constructed for a natural language.