Tree-adjoining grammars

What changes if a grammar combines pieces of trees rather than single variables? Tree-adjoining grammars (TAGs) build derived trees from a finite stock of elementary trees (Joshi et al. 1975; Joshi and Schabes 1997). This change in the basic unit of combination allows one elementary tree to specify relationships that a context-free grammar (CFG) would distribute across several productions.

Reading

Read Joshi and Schabes (1997) through the definition of adjunction.

Elementary trees

A TAG consists of a terminal alphabet, a nonterminal alphabet, a start symbol, and two finite sets of elementary trees:

An initial tree represents a nonrecursive structure. Some of its frontier nodes may be marked for substitution, which we write as $X\!\downarrow$.
An auxiliary tree represents a recursive structure. It has one distinguished frontier node, called the foot node, whose label is identical to the root label. We write the foot as $X^*$.

The grammar combines these trees using substitution and adjunction.

Substitution

Suppose a derived tree contains a frontier node $X\!\downarrow$. If an initial tree has root label $X$, substitution replaces the marked node with that initial tree.

Substitution is thus close to context-free rewriting. It expands a frontier node, and the substituted tree contributes one contiguous span to the derived string.

Adjunction

Suppose an auxiliary tree has root $X$ and foot $X^*$. To adjoin it at an $X$ node in another tree, we:

remove the subtree rooted at that node;
place the auxiliary tree at the node; and
attach the removed subtree at the foot.

The auxiliary tree thereby wraps around an existing subtree. Repeated adjunction can coordinate material on both sides of that subtree, which gives TAG more weak generative capacity than a CFG.

Question

Why must the root and foot of an auxiliary tree have the same label?

Answer

The shared label preserves the category of the adjunction site. An $X$ subtree is replaced by a larger $X$ subtree, so the result can occur wherever the original subtree could occur.

Why adjunction preserves the site

The adjunction-site invariant (ASI) states two things: (i) an adjunction at an $X$ node leaves an $X$-rooted subtree at that position; and (ii) if the removed subtree has yield $w$ and the auxiliary tree contributes terminal yields $u$ and $v$ to the left and right of its foot, the new subtree has yield $uwv$.

To verify the ASI, take a derived tree $t$, an $X$ node $q$ in $t$, and an auxiliary tree $\beta$ whose root and foot are both labeled $X$. The grammar must license $\beta$ at $q$. Matching root, foot, and site labels is necessary for adjunction, but a TAG may impose further selective-adjunction, null-adjunction, or feature-unification constraints. Let $t_q$ be the subtree removed from $q$, and write its yield as $w$. Assume that every substitution site in $\beta$ other than the foot has been filled. Reading the resulting frontier from left to right, write $u$ for the terminal yield contributed before the foot and $v$ for the terminal yield contributed after it. The same argument applies to a partial tree if $u$ and $v$ are understood as frontier contributions rather than terminal strings.

We now trace the construction. Placing $\beta$ at $q$ leaves the root label at that position equal to $X$, because the root of $\beta$ is $X$. Attaching $t_q$ at the foot is permitted because the foot is also $X$. The frontier before the foot contributes $u$, the reattached subtree contributes $w$, and the frontier after the foot contributes $v$. The new local yield is thus $uwv$. All nodes outside $q$ are untouched, so their labels and relative frontier order are unchanged. The two parts of the ASI follow for one adjunction.

Suppose $w=\text{chase rabbits}$, $u=\text{will}$, and $v=\text{today}$. The auxiliary tree has schematic yield $\text{will}\;X^*\;\text{today}$. Adjunction replaces the foot with the original subtree, giving $\text{will chase rabbits today}$, while the root at the adjunction site remains $X$.

The simple yield recurrence applies to repeated root adjunction at the current $X$ subtree. With zero operations, the original subtree and its yield $w_0$ supply the base case. For the inductive step, assume that $k$ licensed root adjunctions leave an $X$ subtree with yield $w_k$. One more licensed auxiliary tree wraps that entire subtree and, by the one-step argument, produces another $X$ subtree with yield $w_{k+1}=u_{k+1}w_kv_{k+1}$. Thus, every finite sequence of licensed root adjunctions preserves the category at that site while adding material around its current yield.

Adjunction at a proper descendant does not generally satisfy this recurrence for the yield of the whole $X$ subtree: it wraps the yield at the descendant site, which may be only one substring of $w_k$. The local ASI still applies at every licensed site, however. Induction on an arbitrary sequence of adjunctions thus preserves the root category at each modified site, while the displayed $u_{k+1}w_kv_{k+1}$ equation is reserved for repeated root adjunction.

Generative capacity and parsing

TAG parsing can be formulated deductively. An item must identify both the outer span of an elementary tree and the gap occupied by an adjoined subtree. The tabular recognition algorithm of Vijay-Shankar and Joshi (1985) runs in $O(n^6)$ time when the TAG is fixed; restrictions on the grammar or later recognition techniques may lower this bound.

The weak generative position of TAG requires some care. TAG, head grammar, linear indexed grammar, and suitably restricted combinatory categorial grammar generate the same string-language class (Vijay-Shanker and Weir 1994). Separately, a binary TAG can be represented as a binary linear context-free rewriting system whose TAG nonterminals have fan-out two (Cohen and Gildea 2016). This is a constrained encoding, not an equivalence with arbitrary binary LCFRS rules: general LCFRSs may use higher fan-out or interleave composition-function arguments in ways the TAG encoding does not. And fan-out-one multiple context-free grammars are just CFGs, while unrestricted multiple context-free grammars generate a larger class. The next section states these containments; the later equivalence-proof section establishes them by explicit translations.

References

Cohen, Shay B., and Daniel Gildea. 2016. “Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication.” Computational Linguistics 42 (3): 421–55. https://doi.org/10.1162/COLI_a_00254.

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-Shankar, K., and Aravind K. Joshi. 1985. “Some Computational Properties of Tree Adjoining Grammars.” 23rd Annual Meeting of the Association for Computational Linguistics (Chicago, Illinois, USA), 82–93. https://doi.org/10.3115/981210.981221.

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

--- title: Tree-adjoining grammars bibliography: ../../references.bib --- What changes if a grammar combines pieces of trees rather than single variables? Tree-adjoining grammars (TAGs) build derived trees from a finite stock of *elementary trees* [@joshi1975tree; @joshi1997introduction]. This change in the basic unit of combination allows one elementary tree to specify relationships that a context-free grammar (CFG) would distribute across several productions. ::: {.callout-note title="Reading"} Read @joshi1997introduction through the definition of adjunction. ::: ## Elementary trees A TAG consists of a terminal alphabet, a nonterminal alphabet, a start symbol, and two finite sets of elementary trees: 1. An *initial tree* represents a nonrecursive structure. Some of its frontier nodes may be marked for substitution, which we write as $X\!\downarrow$. 2. An *auxiliary tree* represents a recursive structure. It has one distinguished frontier node, called the *foot node*, whose label is identical to the root label. We write the foot as $X^*$. The grammar combines these trees using substitution and adjunction. ## Substitution Suppose a derived tree contains a frontier node $X\!\downarrow$. If an initial tree has root label $X$, *substitution* replaces the marked node with that initial tree. Substitution is thus close to context-free rewriting. It expands a frontier node, and the substituted tree contributes one contiguous span to the derived string. ## Adjunction Suppose an auxiliary tree has root $X$ and foot $X^*$. To *adjoin* it at an $X$ node in another tree, we: 1. remove the subtree rooted at that node; 2. place the auxiliary tree at the node; and 3. attach the removed subtree at the foot. The auxiliary tree thereby wraps around an existing subtree. Repeated adjunction can coordinate material on both sides of that subtree, which gives TAG more weak generative capacity than a CFG. ::: {.callout-note collapse="true" title="Question"} Why must the root and foot of an auxiliary tree have the same label? ::: {.callout-tip collapse="true" title="Answer"} The shared label preserves the category of the adjunction site. An $X$ subtree is replaced by a larger $X$ subtree, so the result can occur wherever the original subtree could occur. ::: ::: ### Why adjunction preserves the site The **adjunction-site invariant** (ASI) states two things: (i) an adjunction at an $X$ node leaves an $X$-rooted subtree at that position; and (ii) if the removed subtree has yield $w$ and the auxiliary tree contributes terminal yields $u$ and $v$ to the left and right of its foot, the new subtree has yield $uwv$. To verify the ASI, take a derived tree $t$, an $X$ node $q$ in $t$, and an auxiliary tree $\beta$ whose root and foot are both labeled $X$. The grammar must license $\beta$ at $q$. Matching root, foot, and site labels is necessary for adjunction, but a TAG may impose further selective-adjunction, null-adjunction, or feature-unification constraints. Let $t_q$ be the subtree removed from $q$, and write its yield as $w$. Assume that every substitution site in $\beta$ other than the foot has been filled. Reading the resulting frontier from left to right, write $u$ for the terminal yield contributed before the foot and $v$ for the terminal yield contributed after it. The same argument applies to a partial tree if $u$ and $v$ are understood as frontier contributions rather than terminal strings. We now trace the construction. Placing $\beta$ at $q$ leaves the root label at that position equal to $X$, because the root of $\beta$ is $X$. Attaching $t_q$ at the foot is permitted because the foot is also $X$. The frontier before the foot contributes $u$, the reattached subtree contributes $w$, and the frontier after the foot contributes $v$. The new local yield is thus $uwv$. All nodes outside $q$ are untouched, so their labels and relative frontier order are unchanged. The two parts of the ASI follow for one adjunction. Suppose $w=\text{chase rabbits}$, $u=\text{will}$, and $v=\text{today}$. The auxiliary tree has schematic yield $\text{will}\;X^*\;\text{today}$. Adjunction replaces the foot with the original subtree, giving $\text{will chase rabbits today}$, while the root at the adjunction site remains $X$. The simple yield recurrence applies to **repeated root adjunction** at the current $X$ subtree. With zero operations, the original subtree and its yield $w_0$ supply the base case. For the inductive step, assume that $k$ licensed root adjunctions leave an $X$ subtree with yield $w_k$. One more licensed auxiliary tree wraps that entire subtree and, by the one-step argument, produces another $X$ subtree with yield $w_{k+1}=u_{k+1}w_kv_{k+1}$. Thus, every finite sequence of licensed root adjunctions preserves the category at that site while adding material around its current yield. Adjunction at a proper descendant does not generally satisfy this recurrence for the yield of the whole $X$ subtree: it wraps the yield at the descendant site, which may be only one substring of $w_k$. The local ASI still applies at every licensed site, however. Induction on an arbitrary sequence of adjunctions thus preserves the root category at each modified site, while the displayed $u_{k+1}w_kv_{k+1}$ equation is reserved for repeated root adjunction. ## Generative capacity and parsing TAG parsing can be formulated deductively. An item must identify both the outer span of an elementary tree and the gap occupied by an adjoined subtree. The tabular recognition algorithm of @vijay_shankar_joshi_1985_computational runs in $O(n^6)$ time when the TAG is fixed; restrictions on the grammar or later recognition techniques may lower this bound. The weak generative position of TAG requires some care. TAG, head grammar, linear indexed grammar, and suitably restricted combinatory categorial grammar generate the same string-language class [@vijayshanker1994equivalence]. Separately, a binary TAG can be represented as a binary linear context-free rewriting system whose TAG nonterminals have fan-out two [@cohen_gildea_2016_parsing]. This is a constrained encoding, not an equivalence with arbitrary binary LCFRS rules: general LCFRSs may use higher fan-out or interleave composition-function arguments in ways the TAG encoding does not. And fan-out-one multiple context-free grammars are just CFGs, while unrestricted multiple context-free grammars generate a larger class. The [next section](mcfgs-and-lcfrs.qmd) states these containments; the later [equivalence-proof section](proving-equivalences.qmd) establishes them by explicit translations.