- {Elementary trees in TAG

Recursive structures are represented by AUXILIARY TREES, which
represent constituents that are adjuncts to basic structures (e.g. adverbials).
Auxiliary trees are characterized as follows: 1) all internal nodes are labeled
by non-terminals, 2) all leaf nodes are labeled by terminals, or by
non-terminal nodes marked for substitution, except for exactly one non-terminal
node, called the foot node, which can only be used to adjoin the tree to
another node^{2.1}, 3) the foot node has the same label as the root node of
the tree.
There are two operations defined in the TAG formalism,
substitution^{2.2} and
adjunction. In the SUBSTITUTION operation, the root node on an
initial tree is merged into a non-terminal leaf node marked for substitution in
another initial tree, producing a new tree. The root node and the substitution
node must have the same name. Figure 2.2 shows two initial trees
and the tree resulting from the substitution of one tree into the other.

- {Substitution in TAG

In an ADJUNCTION operation, an auxiliary tree is grafted onto a non-terminal node anywhere in an initial tree. The root and foot nodes of the auxiliary tree must match the node at which the auxiliary tree adjoins. Figure 2.3 shows an auxiliary tree and an initial tree, and the tree resulting from an adjunction operation.

- {Adjunction in TAG

A TAG *G* is a collection of finite initial trees, *I*, and auxiliary trees,
*A*. The TREE SET of a TAG *G*,
is defined to be the
set of all derived trees starting from S-type initial trees in *I* whose
frontier consists of terminal nodes (all substitution nodes having been
filled). The STRING LANGUAGE generated by a TAG,
,
is
defined to be the set of all terminal strings on the frontier of the trees in
.