Multiple Adjunction in Feature-Based
Tree-Adjoining Grammar

Claire Gardent∗
CNRS, LORIA

Shashi Narayan∗
Universit´e de Lorraine, LORIA

In parsing with Tree Adjoining Grammar (TAG), independent derivations have been shown by
Schabes and Shieber (1994) to be essential for correctly supporting syntactic analysis, semantic
interpretación, and statistical language modeling. Sin embargo, the parsing algorithm they propose
is not directly applicable to Feature-Based TAGs (FB-TAG). We provide a recognition algorithm
for FB-TAG that supports both dependent and independent derivations. The resulting algorithm
combines the benefits of independent derivations with those of Feature-Based grammars. en par-
particular, we show that it accounts for a range of interactions between dependent vs. independiente
derivation on the one hand, and syntactic constraints, linear ordering, and scopal vs. nonscopal
semantic dependencies on the other hand.

1. Introducción

A Tree Adjoining Grammar (TAG; Joshi and Schabes 1997) consists of a set of elemen-
tary trees and two combining operations, substitution and adjunction. Como consecuencia, a
TAG derivation can be described by a tree (called a derivation tree) specifying which
elementary TAG trees were combined using which operations to yield that derivation.
In this tree, each vertex is labeled with a tree name and each edge with a description
of the operation (node address and operation type) used to combine the trees labeling
its end vertices. As we shall see in Section 3.2, in TAG, each derivation tree specifies a
unique parse tree, also called derived tree.

In previous work, it has been argued that TAG derivation trees provide a good
approximation of semantic dependencies between the words of a sentence (Kroch 1989;
Rambow, Vijay-Shanker, and Weir 1995; Candito and Kahane 1998; Kallmeyer and
Kuhlmann 2012). As shown by Schabes and Shieber (1994), sin embargo, there are several
possible ways of defining TAG derivation trees, depending on how multiple adjunc-
tion of several auxiliary trees at the same tree node is handled. The standard notion of
derivation proposed by Vijay-Shanker (1987) forbids multiple adjunction, thus enforcing
dependent derivations. A diferencia de, the extended notion of derivation proposed by Schabes

∗ UMR 7503, Campus Scientifique, BP 239, F-54506 Vandoeuvre-l`es-Nancy Cedex, Francia.

Correo electrónico:{claire.gardent,shashi.narayan}@loria.fr.

Envío recibido: 2 Agosto 2013; versión revisada recibida: 16 Junio 2014; accepted for publication:
21 Septiembre 2014.

doi:10.1162/COLI a 00217

© 2015 Asociación de Lingüística Computacional

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ligüística computacional

Volumen 41, Número 1

norte

norte

norte

Adj

∗

norte

Adj

∗

norte

pepper

αpepper

roasted

βroasted

rojo

βred

αpepper
0
βred
0
βroasted
Estándar (dependent)
Derivation

αpepper
0
0

βred

βroasted

Extended (independiente)
Derivation

Cifra 1
An example TAG with the alternative TAG derivations for the phrase roasted red pepper. αpepper,
βred, and βroasted are the elementary trees for pepper (initial tree), rojo (auxiliary tree), and roasted
(auxiliary tree), respectivamente.

and Shieber (1992, 1994) allows multiple adjunction at a single node, thereby yielding
so-called independent derivations (es decir., derivations where the relation between the ad-
joining trees is left unspecified). The difference between the two types of derivations is
illustrated in Figure 1. While in the standard (dependent) derivation, one adjective tree
is adjoined to the other adjective tree, which itself is adjoined to the noun tree for pepper;
in the extended (independiente) derivation, both adjective trees adjoin to the noun tree.

Schabes and Shieber (1994) argue that allowing both for dependent and indepen-
dent derivations better reflects linguistic dependencies. Making use of the distinction in-
troduced in TAG between predicative and modifier auxiliary trees (Schabes and Shieber
(1994), Sección 3.1), they define a parsing algorithm that assigns dependent derivations
to predicative auxiliary trees but independent derivations to multiple modifier auxiliary
trees adjoining to the same node. In case both predicative and modifier auxiliary trees
adjoin to the same node, their parsing algorithm ensures that predicative trees appear
above the modifier trees in the derived tree.

This parsing algorithm is defined for featureless variants of TAG. A diferencia de, en
implemented TAGs (p.ej., XTAG [The XTAG Research Group 2001], SemXTAG [Gardent
2008], or XXTAG1 [Alahverdzhieva 2008]) feature structures and feature unification
are central. They are used to minimize the size of the grammar; to model linguistic
phenomena such as verb/subject agreement; and to encode a unification-based syn-
tax/semantics interface (p.ej., Gardent and Kallmeyer 2003).

In this article, we extend Schabes and Shieber’s proposal to Feature-Based TAG
(FB-TAG); and we show that the resulting parsing algorithm naturally accounts for the
interplay of dependent vs. independent derivation structures with syntactic constraints,
linear ordering, and scopal vs. nonscopal semantic dependencies.

The article is organized as follows. En la sección 2, we recap the motivations for
independent derivations put forward by Schabes and Shieber (1994) and we briefly
discuss the interactions that may arise between dependent and independent deriva-
ciones. Sección 3 summarizes their approach. En la sección 4, we present the intuitions and
motivations underlying our proposal and we highlight the differences with Schabes and
Shieber’s approach. Sección 5 presents our proposal. Sección 6 concluye.

2. Why Are Independent Derivations Desirable?

We start by summarizing Schabes and Shieber’s motivations for independent
derivations. We then discuss the interactions between dependent and independent
derivations.

1 XXTAG stands for XMG (Crabb´e et al. 2013)-based XTAG.

42

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

2.1 Motivations for Independent Derivations

Schabes and Shieber (1994) give three main motivations for independent deriva-
ciones. The first motivation concerns the interaction of verbs with multiple modifiers.
Consider sentences2 in Examples (1) y (2).

(1) a. Richard Parker and Pi wandered the Algae Island yesterday through the

meerkats.

b. Richard Parker and Pi wandered the Algae Island yesterday.

C. Richard Parker and Pi wandered the Algae Island through the meerkats.

(2) a.

The Orangutan reminded Pi of his mother yesterday through the

meerkats.
norte

b. The Orangutan reminded Pi of his mother yesterday.

C.

The Orangutan reminded Pi of his mother through the meerkats.

norte

Movement verbs such as to wander allow for directional modifiers such as through
the meerkats, whereas verbs such as to remind do not. In TAG, such restrictions can be
modeled using selective adjoining constraints to specify which modifier tree may or
may not be adjoined at a particular node in a given tree. Por lo tanto, it is possible to
licencia (1) and to rule out (2C). In Example (2a), sin embargo, under the dependent notion
of adjunction, the tree for the directional adverbial through the meerkats will adjoin to the
modifier tree for yesterday, which itself will adjoin to the tree selected by reminded. De este modo,
constraints placed by the verb on its modifiers must be passed through by modifier trees
(aquí, the tree for yesterday) to also rule out sentences such as Example (2a). Propagating
selective adjunction constraints in TAG would lead to a formalism for which derivation
trees are no longer context-free (Schabes and Shieber 1994).

The second motivation for independent adjunction stems from probabilistic ap-
se acerca. Stochastic lexicalized TAG specifies the probability of an adjunction of a given
auxiliary tree at a given node in another elementary tree (Resnik 1992; Schabes 1992).
De este modo, under the standard notion of derivation, the overall probability of the string
roasted red pepper would be determined by the probability of red adjoining to pepper and
the probability of roasted adjoining to red. A diferencia de, independent adjunction would
result in a derivation such that the overall probability of the string roasted red pepper
would be determined by the probability of both red and roasted adjoining to pepper.
Schabes and Shieber (1994, página 97) argue that it is plausible that “the most important
relationships to characterize statistically are those between modifier and modified,
rather than between two modifiers.”

A third motivation comes from semantics and, more particularly, from scope am-
biguities involving modifiers. Given a sentence such as Example (3), where the relative
scope of the modifiers twice and intentionally is ambiguous,3 Shieber (1994) shows that,
under the extended definition of adjunction, a synchronous TAG modeling the relation
between syntactic trees and logical formulae can account for both readings.

(3) John blinked twice intentionally.

2 The characters in these sentences are borrowed from Yann Martel’s book Life of Pi.
3 The sentence can describe either a single intentional act of blinking twice or two intentional acts each of single

blinking (Shieber 1994).

43

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ligüística computacional

Volumen 41, Número 1

The account crucially relies on multiple independent adjunction of the two mod-
ifier trees to the tree for blink: Depending on which order the auxiliary trees for twice
and intentionally adjoins to blink, the logical formula built will be either intention-
ally(twice(blink)) or twice(intentionally(blink)), thus capturing the ambiguity.

2.2 Dependent, Independent, and Mixed Derivations

To capture the different types of semantic dependencies and morpho-syntactic con-
straints that may hold between multiple auxiliary trees adjoining to the same entity,
both dependent and independent derivations are needed.

As argued earlier, because there are no constraints or semantic relation holding
between each of them, multiple intersective modifiers applying to the same entity
(Ejemplo (4)) are best modeled using an independent derivation.

(4) The tall black meerkat slept.

(Independent derivation)

A diferencia de, because they may involve strong scopal and morpho-syntactic
constraints, stacked predicative verbs (es decir., verbs taking a sentential complement,
Ejemplo (5a)) and non-intersective modifiers (Ejemplo (5C)) require dependent deriva-
ciones. Consider sentences (5a–b), por ejemplo. If predicative trees were assigned an
independent derivation, oración (5a) would be judged ungrammatical (because want
requires an infinitival complement but would adjoin to the finite verb slept) y estafa-
versely, oración (5b) would incorrectly be judged grammatical (because both want
and try require an infinitival complement). Similarmente, in Example (5C), the church is
Syrian Orthodox, not Syrian and Orthodox. Assigning a dependent rather than an inde-
pendent derivation to such cases straightforwardly captures the distinction between
intersective and non-intersective modifiers.

(5) a. XJohn wanted to assume that Peter slept.
John wanted Peter tries to walk.

b.

(Dependent derivation)

C. The meerkat admired the Syrian Orthodox church.

norte

(Dependent derivation)

Finalmente, some multiple adjunctions may involve both dependent and independent
derivations, Por ejemplo, when multiple modifiers and predicative verbs adjoin to the
same verb (Ejemplo (6a)) or in the case of a derivation (Ejemplo (6b)) involving both
intersective (viejo) and non-intersective (es decir., Syrian in Syrian Orthodox) modifiers.

(6) a. Yann said that John knows that Richard Parker and Pi wandered the Algae
(Mixed derivation)

Island yesterday through the meerkats.

b. The meerkat admired the old Syrian Orthodox church.

(Mixed derivation)

As we shall see in Section 5.3, the parsing algorithm we propose licenses depen-
mella, independiente, and mixed derivations but is restricted to appropriately distinguish
between various types of modifiers. Además, the feature information encoded in the
grammar further restricts the derivation structures produced, thereby accounting for
the interactions between adjunction, linear ordering, and morpho-syntactic constraints.

3. Multiple Adjunction in Tree Adjoining Grammars

Vijay-Shanker and Weir (1991) introduce a compilation of TAG to Linear Indexed
Grammars (LIGs; Gazdar 1988) that makes the derivation process explicit. Schabes and

44

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

Shieber (1994) modify this compilation to allow for both dependent and independent
derivations. The resulting LIG is further exploited to specify a parsing algorithm that
recovers those derivations.

En esta sección, we summarize Schabes and Shieber’s proposal. We start (Sección 3.1)
with an informal description of their approach. En la sección 3.2, we introduce ordered
derivation trees. Sección 3.3 provides a brief introduction to LIG. Sección 3.4 summa-
rizes the TAG-to-LIG compilation proposed by Vijay-Shanker and Weir (1991). Finalmente,
Sección 3.5 describes the modifications introduced by Schabes and Shieber (1994) a
allow both for dependent and for independent derivations.

3.1 Schabes and Shieber’s Proposal: Motivations and Intuitions

Tree Adjoining Grammar distinguishes between two types of auxiliary trees, a saber,
modifier vs. predicative auxiliary trees (Joshi and Vijay-Shanker 2001). Whereas pred-
icative trees are assigned to verbs taking a sentential argument, modifier trees are
assigned to all other auxiliary trees (p.ej., verbal auxiliaries, adjectives, adverbs, prepo-
sitions, and determiners). More generally, the difference between a predicative and a
modifier tree is that in a predicative tree, the foot node, like the substitution nodes, corre-
sponds to an argument node selected by its lexical anchor (es decir., the word that selects that
árbol) whereas in a modifier auxiliary tree, the foot node is an open slot corresponding
to the phrase being modified. When associating semantic entities with tree nodes (como
propuesto, Por ejemplo, by Joshi and Vijay-Shanker [2001] and Gardent and Kallmeyer
[2003]), this difference can be seen by noting the entities associated with root and foot
nodos: These are distinct in a predicative tree but identical in modifier trees.

In their approach, Schabes and Shieber specify a TAG-to-LIG conversion that sys-
tematically associates dependent derivations with predicative auxiliary trees and in-
dependent derivations with modifier auxiliary trees. Además, they introduce two
mechanisms to ensure that each derivation tree unambiguously specifies a linguistically
plausible derived tree.

Primero, they enforce ordering constraints between modifier trees adjoining at the same
nodo (which are thus ambiguous with respect to the derived tree they describe) por
assuming that derivation trees are ordered and that linear precedence (LP) statements
can be used to constrain the order of siblings in a derivation tree. Por ejemplo, given
the independent derivation shown in Figure 1, an LP statement stating that βred must
occur before βroasted in the derivation tree will ensure that βroasted appears above βred in
the derived tree and therefore that the resulting derived tree yields the phrase roasted
red pepper rather than red roasted pepper.

Segundo, when both predicative and modifier trees adjoin at the same address,
predicative trees always occur above all modifier trees in the derived tree (“outermost
predication”). This ensures, por ejemplo, that under the reading where yesterday refers
to the arriving rather than the saying (es decir., when both say and yesterday adjoin to arrive),
Ejemplo (7a) is derived but not Example (7b).

(7) a. XPeter says that yesterday John arrived late.
Yesterday Peter says that John arrived late.

b.

3.2 Ordered Derivation Trees

norte

In the standard version of TAG, each derivation tree describes a unique derived tree.
In the case of a dependent derivation, unicity follows from the fact that dependent

45

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ligüística computacional

Volumen 41, Número 1

t

gramo

gramo

gramo

β1

βi

βn

t
gramo

βn

βi

β1

t

Cifra 2
Ordered derivation tree and corresponding derived tree. t, β1, βi, and βn are elementary trees.
β1, βi, and βn are auxiliary trees that all adjoin at the address g in the elementary tree τ.

derivations specify the order in which adjunction takes place (p.ej., β2 adjoins to β1
and the result to α). Como resultado, if β2 adjoins to β1, there is only one possible derived
tree—namely, a tree where β2 appears above β1.

When allowing for independent derivations, sin embargo, several derived trees are
posible, depending on the order in which the auxiliary trees are adjoined. To ensure
a unique mapping from derivation to derived tree, Schabes and Shieber (1994) por lo tanto
introduce the notion of ordered derivation trees. Ordered derivation trees differ from
standard TAG derivation trees in that (i) they may contain sibling edges labeled with
the same address, y (ii) they specify a total order on such siblings.

Cifra 2 shows an example ordered derivation tree and associated derived tree.
As indicated by the shared g address on their parent edge, auxiliary trees β1, . . . , βn
adjoin to the same node—namely, the node with address g in the elementary tree τ.
Because the derivation tree is ordered, β1 will appear below β2 in the derived tree,
which in turn will be below β3, etcétera. En breve, given a set of auxiliary trees all
adjoining to the same tree node, the derived tree produced from an ordered derivation
tree following an independent derivation will be identical to the derived tree produced
with the corresponding dependent derivation—that is, the dependent derivation where
β1, . . . , βn appear in increasing index order from top to bottom.

3.3 Linear Indexed Grammar

Like context-free grammars, LIGs (Gazdar 1988) are string rewriting systems where
strings are composed of terminals and nonterminals. In a LIG, sin embargo, nonterminal
symbols may be associated with a stack of symbols, called indices. A LIG rule can thus
be represented as follows:

norte[..µ] → N1[µ1] . . . Ni−1[µi−1]En[..µi]Ni+1[µi+1] . . . Nn[µn]

(8)

N and Ni are nonterminals whereas µ and µi are strings of stack symbols. The symbol ..
stands for the remainder of the stack symbols. Note that the remainder of the stack sym-
bols associated with the left-hand side is associated with only one of the nonterminal
(a saber, En) on the right-hand side.

46

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

LIGs have been used in the literature (Weir and Joshi 1988; Vijay-Shanker and Weir
1991) to provide a common framework for the extensions of context-free grammars. En
particular, Vijay-Shanker and Weir (1991, 1993) showed a weak equivalence between
LIGs, TAGs, and combinatory categorial grammars (Steedman 2000) and proposed
a LIG-based polynomial-time CYK recognition algorithm for TAGs and combinatory
categorical grammars. In what follows, we show how Schabes and Shieber (1994) use a
LIG variant of TAGs to license both dependent and independent derivations.

3.4 TAG to LIG Compilation

The TAG-to-LIG compilation proposed by Vijay-Shanker and Weir (1991) produces
LIG rules that simulate a traversal of the derived tree produced by the original TAG
gramática. In these LIG rules, each node η of a TAG elementary tree is viewed as having
both a top t[..η] and a bottom b[..η] component to account for the possibility of an
adjunction. Cifra 3 illustrates the traversal of the TAG-derived trees specified by the
LIG resulting fromVijay-Shanker and Weir (1991) TAG-to-LIG compilation.

Cifra 4 lists the LIG rules resulting from the TAG to LIG compilation process. Cada
nonterminal (t[..η] or b[..η]) with the top of the stack symbol in a LIG rule corresponds
to a unique node in some elementary tree of the grammar. The inner stack symbols are
used to keep track of the nodes higher in the derived tree where an auxiliary tree has
been adjoined.

Rules of Types 1 y 2 capture immediate dominance between the bottom of a
node η and the top of its immediate daughters in two configurations, depending on
whether η dominates the foot node (Tipo 1) or not (Tipo 2). Rules of Type 3 handle
nodes that require neither substitution nor adjunction. This rule handles cases where
no adjunction occurs at a node by rewriting the top of this node to its bottom. Rules
of Type 6 model substitution. Finalmente, rules of Types 4 y 5 handle adjunction. Ellos
specify that, for any given node η and any auxiliary tree β that may adjoin to η, el
top of η rewrites to the top of the root node of β; and the bottom of the foot of β to
the bottom of η. It follows that there can be no multiple adjunction in this LIG version
of TAG.

Tipo 4

t[η]

b[η]

Tipo 3

Tipo 1/2

Tipo 5

t[η1]

t[ηi]

t[ηn]

t[ηηr]

b[ηηr]

b

t[ηηf ]

b[ηηf ]

Cifra 3
LIG variant of TAG for the Standard derivation. Each of the tree nodes in the grammar is
assigned a unique address. Por ejemplo, here η, η1, ηi, and ηn point to the distinct nodes in the
left elementary tree and ηr and ηf point to the root and the foot nodes of the shown auxiliary
tree β in the grammar. t[..η] and b[..η] are the top and bottom components of the tree node η in
the grammar.

47

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ligüística computacional

Volumen 41, Número 1

Tipo 1: Immediate domination dominating foot. For each node η in the auxiliary trees that dominates the
foot node and with children η1, . . . , ηi, . . . , ηn, where the child ηi also dominates the foot node, el
following LIG production rule is generated.

b[..η] → t[η1] . . . t[ηi−1]t[..ηi]t[ηi+1] . . . t[ηn]

Tipo 2: Immediate domination not dominating foot. For each elementary tree node η that does not dominate
the foot node and with children η1, . . . , ηn, the following LIG production rule is generated.

b[η] → t[η1] . . . t[ηn]

Tipo 3: No adjunction. For each elementary tree node η that is not marked for substitution or obligatory

adjunction, the following LIG production rule is generated.

t[..η] → b[..η]

Tipo 4: Start root of adjunction. For each elementary tree node η that allows the adjunction of the auxiliary

tree with the root node ηr, the following LIG production rule is generated.

t[..η] → t[..ηηr]

Tipo 5: Start foot of adjunction. For each elementary tree node η that allows the adjunction of the auxiliary

tree with the foot node ηf , the following LIG production rule is generated.

Tipo 6: Start substitution. For each elementary tree node η that allows the substitution of the initial tree

with the root node ηr, the following LIG production rule is generated (not shown in Figure 3).

b[..ηηf ] → b[..η]

Cifra 4
LIG production rules for the Standard derivation.

t[η] → t[ηr]

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

3.5 Modifying the TAG to LIG Compilation to Allow for Multiple Adjunctions

To associate predicative tree adjunctions with dependent derivations and multiple mod-
ifier adjunctions with independent derivations, Schabes and Shieber (1994) modify the
compilation of TAG to LIG, proposed by Vijay-Shanker and Weir (1991) as sketched
En figura 5. Tipo 4(a) rules apply to adjunctions involving predicative trees. Ellos son
identical to Type 4 rules in the Vijay-Shanker and Weir’s approach and therefore enforce
a standard (dependent) derivation for predicative trees. A diferencia de, Tipo 4(b) normas
apply to adjunctions involving modifiers and result in an independent derivation.

Note also that the Outermost Predication constraint (es decir., predicative trees always
occur above modifier trees adjoined at the same node) alluded to in Section 3.1 follows
from the interactions between the Type 4(a) and Type 4(b) LIG rules.

Schabes and Shieber prove the weak-generative equivalence of TAGs under both
Standard and Extended derivation using the LIG compilation. They also propose a
recognition and a parsing algorithm with complexity of O(n6) in the length of the string.

4. Multiple Adjunction in Feature-Based TAG

En esta sección, we explain why a straightforward extension of Schabes and Shieber’s
proposal to FB-TAG would not work and we outline the intuitions and motivations
underlying our approach. Sección 5 will then introduce the details of our proposal.

48

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

Tipo 4(a)

βpred

Tipo 4(b)

βmod

predicative tree

modifier tree

Tipo 4(a): Start root of adjunction for predicative trees. For each elementary tree node η that allows the
adjunction of the predicative auxiliary tree with the root node ηr, the following LIG production
rule is generated.

Tipo 4(b): Start root of adjunction for modifier trees. For each elementary tree node η that allows the
adjunction of the modifier auxiliary tree with the root node ηr, the following LIG production rule
is generated.

t[..η] → t[..ηηr]

b[..η] → t[..ηηr]

Cifra 5
LIG variant of TAG for Schabes and Shieber’s Extended derivation and associated production
normas. The top and bottom components of the nodes are presented by •. Tipo 4(a) transitions
support dependent derivations, and Type 4(b) transitions support independent derivations.

4.1 Feature-Based Tree Adjoining Grammar

We start by a brief description of FB-TAG and of the unifications performed during
derivation. FB-TAG was introduced by Vijay-Shanker (1987) and Vijay-Shanker and
Joshi (1988, 1991) to support the use of feature structures in TAG. Cifra 6 shows a
toy FB-TAG for illustration.

An FB-TAG differs from a TAG in that tree nodes are decorated with feature
estructuras. Nonterminal and foot nodes are decorated with two feature structures called
arriba (t) and bottom (B), and substitution nodes are decorated with a single top feature
estructura. During derivation, feature structure unification constrains tree combination,
as illustrated in Figure 7. Substitution unifies the top feature structure of a substitution
node with the top feature structure of the root node of the tree being substituted. El
adjunction of an auxiliary tree β to a tree node ηo unifies the top and bottom feature
structures of ηo with the top feature structure of the root node of β and the bottom
feature structure of its foot node, respectivamente. Finalmente, at the end of the derivation, el
top and bottom feature structures of all nodes in the derived tree are unified.

notario público[]

[det:todo]

notario público[]

[det:el]

Det NP*[]
[]

Det NP*[det:nil]

[]

todo

el

notario público[]
[]

meerkat

βall
Cifra 6
A toy FB-TAG. For the sake of clarity, feature structures are abbreviated.

βthe

αmeerkat

49

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ligüística computacional

Volumen 41, Número 1

ηr

ηr.T
ηr.B

a

ηo.T

ηo ↓

=⇒

substitution

ηor

ηo.T ∪ ηr.T
ηr.B

ηr

ηr.T
ηr.B

b

ηf

ηf .T
ηf .B

ηor

ηo.T ∪ ηr.T
ηr.B

ηo

ηo.T
ηo.B

=⇒

adjunction

ηof

ηf .T
ηo.B ∪ ηf .B

Cifra 7
Feature unifications along substitution and adjunction in FB-TAG. The node ηo in some
elementary tree τ is the operation site for a substitution or an adjunction. For the sake of
clarity, we only show the operation node ηo.

notario público[]

[det:todo]

notario público[]

[det:el]

βall

NP*[]
[]

βthe

=⇒

NP*[det:nil]
[]

notario público[]

[det:todo]

βall

notario público[]

[det:el]

βthe

NP*[det:nil]
[]

notario público[]
[]

αmeerkat

notario público[]

[det:todo]

βall

notario público[]

[det:el]

=⇒

βthe
notario público[det:nil]
[]

αmeerkat

∪

∪

∪

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

Cifra 8
Standard derivation for all the meerkats.

Cifra 8 shows the standard derivation for the phrase all the meerkats, using the
grammar shown in Figure 6, y figura 9 shows the corresponding derived and deriva-
tion trees. As can be seen, the feature constraints encoded in the grammar correctly
ensure that all the meerkats can be derived (leftmost derivation tree in Figure 9) pero no
the all meerkats (rightmost in Figure 9). The incorrect derivation is blocked by the feature
estructura [det : nil] on the foot of the auxiliary tree βthe, which leads to a unification
failure if βthe is adjoined at the root of βall with bottom feature structure [det : el].

4.2 Why a Simple Extension of the LIG Framework to FB-TAG Will Not Work

To motivate our approach, we start by considering a simple extension of Schabes
and Shieber’s LIG framework to FB-TAG, where each LIG rule enforces unifications
mimicking those applied in FB-TAG. En particular, let us assume that Type 3 normas

notario público

αmeerkat

αmeerkat

Det

notario público

todo

Det

notario público

el

meerkat

βthe

βall

X

βall

βthe

Cifra 9
The derived tree (izquierda), the successful standard derivation tree (middle), and the failed
dependent derivation tree (bien) for all the meerkats.

norte

50

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

NPm

NPm.T : []
NPm.B : []

αmeerkat

(Tipo 4(b))

(Tipo 4(b))

NPthe

NPthe.T : []
NPthe.B : [det : el]

(Tipo 3)

βthe

∗
notario público
el

∗
the.T : [det : nil]
notario público
∗
the.B : []
notario público

NPall

NPall.T : []
NPall.B : [det : todo]

(Tipo 3)

βall

∗
notario público
todo

∗
all.T : []
notario público
∗
all.B : []
notario público

Cifra 10
Failed derivation under a simple extension of the Schabes and Shieber LIG framework to
FB-TAG: Tipo 4(b) rules unify NPm.T with both NPthe.T and NPall.T while Type 3 rules unify
NPthe.T with NPthe.B and NPall.T with NPall.B. Hence NPthe.B and NPall.B should unify.
Sin embargo, because their det values differ, derivation fails.

(“No adjunction”) unify the top and the bottom feature structures of nodes where no
adjunction occurs, and Type 4(b) normas (“Start root of adjunction”) unify the top feature
(η.T) of the node (η) being adjoined to with the top feature structure (ηr.T) of the root
nodo (ηr) of the auxiliary tree being adjoined:4

b[..η] → t[..ηηr]
t[..η] → b[..η]

η.T ∪ ηr.T
η.T ∪ η.B

(Type 4b)

(Tipo 3)

(9)

(10)

As shown in Figure 10, this approach can incorrectly lead to derivation failures
in the case of an independent multiple adjunction. Intuitivamente, the reason for this is
eso, in Schabes and Shieber’s approach, multiple adjunction starts and ends from
the bottom component of the node being adjoined to. This is fine when no features
are involved because the category of the node being adjoined to is always identical
to the root and foot node of the auxiliary trees being adjoined. When nodes carry
feature structures, sin embargo, a unification clash can occur that makes derivation fail.
De este modo, in our example, derivation incorrectly fails because the bottom feature structures
of the root node of the auxiliary tree for all and the bottom feature structure of the
root node of the auxiliary tree for the should unify but have conflicting value. Como
shown by the dependent derivation for all the meerkats depicted in Figure 8, this is
incorrect.

4.3 Proposal: Intuition and Motivations

As we just saw, in the case of multiple independent adjunctions, a straightforward
extension of Schabes and Shieber’s LIG framework to FB-TAG fails to correctly cap-
ture the unification constraints encoded in the grammar. More generally, when ex-
tending multiple independent adjunction to FB-TAG, it is crucial that the feature
constraints encoded by the linguist describe the same set of derived trees no matter

4 We associate η.T ∪ ηr.T with the Type 4(b) rules to mimic the adjunction in FB-TAG, as shown in Figure 7.

51

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ligüística computacional

Volumen 41, Número 1

ηr1

ηr1.T
ηr1.B

β1

ηf 1

ηr2

β2

ηf 2

ηf 1.T
ηf 1.B
ηr2.T
ηr2.B

ηf 2.T
ηf 2.B

ηo

ηo.T
ηo.B =⇒

ηr2

ηr2.T
ηr2.B

ηor1

ηo.T ∪ ηr1.T
ηr1.B

β2

ηf 2

ηf 2.T
ηf2.B

=⇒

ηof 1

ηf 1.T
ηo.B ∪ ηf 1.B

ηor1r2

ηo.T ∪ ηr1.T ∪ ηr2.T
ηr2.B

ηor1f 2

ηf 2.T
ηr1.B ∪ ηf2.B

η0

β1

t

η0

β2

ηof 1

ηf 1.T
ηo.B ∪ ηf 1.B

Ordered
Derivation Tree

Derived Tree

Cifra 11
Independent derivation and feature unification. The unifications performed by the independent
adjunction of β1 and β2 to ηo are the same as those that would be performed by a dependent
adjunction of β2 to β1 and of the resulting derived tree to ηo. Crucially in the independent
derivation, although both β1 and β2 adjoin to ηo, the adjunction of β2 requires access to the
feature structure of the root of β1 (ηf2.B ∪ ηr1.B).

which derivation tree is produced. We therefore propose a parsing algorithm that, given
several auxiliary trees β1, . . . , βn adjoining at the same node ηo, performs the same
unifications independently of whether the derivation is dependent, independiente, o
mixed dependent/independent.

Cifra 11 shows the unifications resulting from the multiple adjunction of β1 and β2
to a single node ηo. While it depicts the unifications enforced by our parsing algorithm
for the derivation tree shown on the right hand side (es decir., for the independent adjunction
of β1 and β2 to ηo), these unifications are in fact exactly the same as those that would be
enforced by a dependent adjunction of β2 into β1 into ηo.

One key point illustrated by Figure 11 is that whereas multiple adjunction operates
on a single node (here ηo), the unification constraints of FB-TAG require that the bottom
feature structure of the foot of an auxiliary tree which appears higher in the derived
árbol (aquí, β2) unifies with the bottom feature structure of the root of the auxiliary
tree appearing immediately below it in the derived tree (here β1)—not with that of
the root of the node to which it adjoins (here ηo). En otras palabras, while a multiple
adjunction on ηo operates on ηo only, a correct implementation of FB-TAG unification
constraints requires keeping track of the feature structures associated with the auxiliary
trees successively adjoining to ηo.

In our proposal, we capture this bookkeeping requirement by associating tree nodes
not with feature structures but with reference variables pointing to feature structures.
The parsing algorithm is then specified so as to support dependent, independiente, y
mixed derivations while enforcing the same unifications as would be performed under
a dependent adjunction.

4.4 Comparison With Schabes and Shieber’s Approach

Before giving the technical details of our parsing algorithm (Sección 5), we first highlight
some differences between our and Schabes and Shieber’s approach. En particular,
we show that (i) whereas Schabes and Shieber resort to three distinct mechanisms
to account for word order constraints (es decir., selective adjoining constraints, linear

52

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

precedence statements on derivation trees, and a constraint on parsing), the FB-
TAG approach supports a uniform treatment of word order and (ii) our approach
straightforwardly accounts for mixed dependent/independent derivations that would
require some additional stipulation in Schabes and Shieber’s approach.

4.4.1 Ordering Constraints among Modifier Auxiliary Trees. In TAG, determiners and verbal
auxiliaries are modifier rather than predicative auxiliary trees (cf. Sección 3.1). Porque
Schabes and Shieber’s definitions systematically associate modifiers with independent
derivations, all examples in (11a–d) undergo an independent derivation and constraints
must therefore be provided to determine the order of the sibling nodes in the resulting
derivation tree.
(11) a. XThe sonatas should have been being played by Sarah.
The sonatas have should been being played by Sarah.

b.
C. XAll the meerkats
The all meerkats
d.

norte

norte

To specify these constraints on similar cases (soft ordering constraints on adjectives
and strict ordering constraints on temporal and spatial adverbial phrases in German),
Schabes and Shieber (1994) suggest the use of LP constraints on derivation tree siblings.
As illustrated by the derivation of Example (11c–d) in Figures 8 y 9, in the FB-
TAG approach, such additional constraints are unnecessary: They simply fall out of the
feature constraints encoded in the grammar.

Note that even if determiners and auxiliary verbs were to be handled using depen-
dent adjunction, the word ordering constraints used by Schabes and Shieber would fail
to account for cases such as Example (12), where auxiliary verbs are interleaved with
adverbs.

(12) John has often been selected for nomination.

En este caso, if the auxiliary verbs has and been were treated as predicative trees,
Schabes and Shieber’s constraint that predicative trees adjoin above modifier trees
would preclude the derivation of Example (12) and incorrectly predict the derived
sentence to be John has been often selected for nomination.

4.4.2 Ordering Constraints among Predicative Trees. As discussed by Schabes and Shieber
(1994), auxiliary predicative trees may impose different constraints on the type of sen-
tential complement they accept. Thus Example (13a) is correct but not Example (13b)
because want expects an infinitival complement (previously shown in Example (5)).
(13) a. XJohn wanted to assume that Peter slept.

b.

John wanted Peter tries to walk.

norte

Although in the Schabes and Shieber’s approach, selective adjoining constraints are
used to license Example (13a) and rule out Example (13b), in the FB-TAG approach, este
can be achieved using feature constraints.

4.4.3 Ordering Constraints between Predicative and Modifier Auxiliary Trees. In sentences
such as Example (14a) where both modifier and predicative auxiliary trees adjoin to the
same address, the predicative trees should generally adjoin above any modifier trees so
that the predicative verb precedes the modifier in the derived string.

53

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ligüística computacional

Volumen 41, Número 1

(14) a. XJohn promised that Peter will leave tomorrow.
Tomorrow John promised that Peter will leave.

b.

norte

To ensure the appropriate linearization, the Schabes and Shieber’s approach intro-
duces the outermost-predication rule, which stipulates that predicative trees adjoin
above modifier auxiliary trees. A diferencia de, the FB-TAG approach allows both orders
and lets feature constraints rule out ungrammatical sentences such as Example (14b).
This allows the approach to directly extend to a counter-example discussed by Schabes
and Shieber (1994), where a modifier (aquí, At what time) must in fact adjoin above a
predicative tree.

(15) At what time did Brockway say Harrison arrived?

Cifra 12 shows two possible derivation trees for the sentence (15) under the
interpretation where it is the time of arriving (rather than the time of saying) cual
is questioned. These derivation trees show the two possible relative orderings of
el (predicative) auxiliary tree for say and the (modifier) auxiliary tree at what time.
Because the Outermost-Predication rule requires that predicative trees adjoin above
modifier trees (and thus occur outermost in the derivation tree), in Schabes and
Shieber’s approach, only the right-hand side derivation is possible, thus failing to
derive sentence (15). A diferencia de, because our approach does not explicitly constrain the
relative ordering of predicative and modifier auxiliary trees adjoining to the same node,
both derivations are possible, thereby licensing both Example (15) and the sentence
Did Brockway say at what time Harrison arrived?

4.4.4 Mixed Dependent and Independent Multiple Adjunctions. In Schabes and Shieber’s
acercarse, all modifier auxiliary trees undergo independent derivation. As shown in
Sección 2.2, sin embargo, non-intersective modifiers arguably license a dependent deriva-
tion while some cases of multiple adjunction may involve both a dependent and an
independent derivation. As we shall see in Section 5, our FB-TAG approach accounts
for such cases by allowing both for independent and dependent derivations, by ruling
out dependent derivations for intersective modifiers and by using feature constraints to
regulate the interactions between multiply adjoining auxiliary trees.

5. Extending Schabes and Shieber’s LIG Framework for FB-TAGs

We now propose a compilation of FB-TAG-to-LIG that makes both dependent and
independent derivations in FB-TAG explicit. We use this resulting LIG to specify an

At what time did Brockway say Harrison arrived?

Did Brockway say at what time Harrison arrived?

arrive

arrive

decir

en

harrison

en

decir

harrison

Brockway

qué

tiempo

qué

tiempo

Brockway

Cifra 12
Ordered derivation trees for the sentence of Example (15). Dotted lines indicate substitutions
and plain lines indicate adjunctions. Schabes and Shieber’s Outermost Predication principle
rules out a derivation tree on the left-hand side.

54

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

Earley algorithm for recovering multiple adjunctions in FB-TAG. This compilation
differs in two main ways from that proposed by Schabes and Shieber (1994). Primero, árbol
nodes are associated with reference variables pointing to feature structures. Segundo, el
LIG rules are modified and extended with unification operations.

5.1 Feature Structures and Reference Variables

To account for FB-TAG unifications while allowing for independent derivations, we re-
place the feature structures of FB-TAG with reference variables pointing to those feature
estructuras. Each node in the elementary trees is decorated with two reference variables:
The top reference variable PT contains the reference to the top feature structure T and
the bottom reference variable PB contains the reference to the bottom feature structure
B. The top and the bottom feature structures of a node η can be traced by val(η.PT) y
vale(η.PB), respectivamente, where PT and PB are the top and the bottom reference variables
decorating the node η, and the function val(PAG) returns the feature structures referred to
by the reference variable P.

When specifying the parsing algorithm, we use reference variables to ensure the
appropriate unifications, como sigue. In an independent derivation where the node ηo
is adjoined to, first by β1 and second by β2, the bottom feature structure ηo.B of ηo (i)
unifies with the bottom feature structure ηf 1.B of the foot of β1 and (ii) is reassigned (:=)
to the bottom reference variable ηr1.PB of the root of β1. When β2 is adjoined, its foot
node will therefore correctly be unified, not with the bottom feature structure of ηo but
with that of ηr1.

5.2 LIG Rules with Unification Operations

To support both dependent and independent derivations while enforcing the correct
unifications, we modify the TAG-to-LIG compilation in such a way that the resulting
LIG rules capture the tree traversal depicted in Figure 13. Independent derivations are
accounted for by the fact that adjunction starts and ends at the bottom component of
the node being adjoined to (Tipo 4 y 5 normas). Our LIG compilation automatically
supports dependent derivations by allowing sequential adjunctions at the roots of
auxiliary trees.

Tipo 3(b)

t[η]

b[η]

Tipo 1/2

t[η1]

t[ηS]

t[ηn]

Tipo 4

Tipo 5

Tipo 3(a)

t[ηηr]

b[ηηr]

t[ηηf ]

b[ηηf ]

Cifra 13
LIG variant of TAG for the extended derivation in FB-TAG.

55

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ligüística computacional

Volumen 41, Número 1

Tipo 4: Start root of adjunction. For each elementary tree node η that allows the adjunc-
tion of the auxiliary tree with the root node ηr, the following LIG production rule
is generated.

b[..η] → t[..ηηr]

vale(η.PT) ∪ val(ηr.PT), η.PB := ηr.PB

Tipo 5: Start foot of adjunction. For each elementary tree node η that allows the adjunc-
tion of the auxiliary tree with the foot node ηf , the following LIG production rule
is generated.

b[..ηηf ] → b[..η]

vale(η.PB) ∪ val(ηf .PB)

Tipo 6: Start substitution. For each elementary tree node η that allows the substitution
of the initial tree with the root node ηr, the following LIG production rule is
generated (not shown in Figure 13).

t[η] → t[ηr]

vale(η.PT) ∪ val(ηr.PT)

To perform multiple adjunction while enforcing the appropriate feature unifications
(as depicted in Figure 11), we split Type 3 rules into two subtypes. Tipo 3(a) normas
apply to the root of auxiliary trees and perform no unification. By no unification, ellos
ensure that feature structures are not blocked for the possibility of the adjunction of
the following auxiliary tree and allow for the correct unifications to be carried out for
independent derivations. Tipo 3(b) rules function as termination of multiple adjunction
by unifying the top and bottom feature structures of the node. It is applicable to all tree
nodes except roots of auxiliary trees.

Tipo 3(a): Terminating adjunction at the root of the auxiliary tree. For each root node η of

the auxiliary trees, the following LIG production rule is generated.

t[..η] → b[..η]

∅

Tipo 3(b): Terminating adjunction at any other node. For each node η that is not a root
node of some auxiliary tree and is not marked for substitution, the following LIG
production rule is generated.

t[..η] → b[..η]

vale(η.PT) ∪ val(η.PB)

Given this set of rules, both dependent and independent derivations are possible.
Por ejemplo, given two auxiliary trees β1 and β2 adjoining at the node η in an ele-
mentary tree τ, a dependent derivation will occur whenever the Type 4 rule applies to
predict the adjunction of, Por ejemplo, β2 at the root of β1. En cambio, if the Type 3(a)
rule applies at the root of β1, recognition will move from the top of the root of β1 to
its bottom, allowing for Type 5 rule to complete the adjunction of β1 at the node η; y
the Type 4 rule applies to predict the adjunction of β2 at the node η of τ, registering an
independent derivation.

56

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

5.3 Parsing Algorithm

En esta sección, we present our parsing algorithm for FB-TAGs with dependent and in-
dependent derivations. We start with an informal description of how the algorithm han-
dles the interactions between unification and independent derivations. We then go on
to specify the inference rules making up the algorithm. We do this in two steps. Primero, nosotros
present a basic set of rules allowing for both dependent and independent derivations.
Segundo, we show how to constrain this algorithm to minimize spurious ambiguity.

5.3.1 Independent Derivations and Feature-Structure Unification. Before specifying the pars-
ing algorithm, we illustrate by means of an example the interplay between multiple
independent adjunction and feature structure unifications.

Cifra 14 displays the feature unifications and reassignment performed during the
recognition process of a multiple independent adjunction. The linear ordering of the
equations reflects the order of the parsing completion operations.

Given the auxiliary tree β1 and the adjunction site ηo, the picture shows that unify-
ing the bottom feature structure of the foot node of β1 with the bottom feature structure
of ηo (Step 1: Tipo 5, ηo.B ∪ ηf 1.B) occurs before the bottom reference variable of ηo is re-
assigned to the bottom feature structure of the root of β1 (Step 4: Tipo 4, ηo.PB → ηr1.B).
También, the reassignment ensures that the follow-up adjunction of β2 at the node ηo
has access to the bottom feature of the root of the previous auxiliary tree β1 (Step 5:
Tipo 5, ηr1.B ∪ ηf 2.B). At the end of the adjunction (Step 9), the Type 3(b) rule ensures
that the top and the bottom features of the root of the last auxiliary tree (aquí, β2)
adjoined are unified (ηr2.T ∪ ηr2.B).

ηo.PT → ηo.T
ηo.PB → ηo.B

ηo

t
b

(9)

(8)

(4)

(3)

t
b

ηr1

ηr1.PT → ηr1.T
ηr1.PB → ηr1.B

(7)

t
b

ηr2

ηr2.PT → ηr2.T
ηr2.PB → ηr2.B

β1

β2

(1)

(2)

ηf 1

t
b

ηf 1.PT → ηf 1.T
ηf 1.PB → ηf 1.B

(6)

ηf 2

t
b

ηf 2.PT → ηf 2.T
ηf 2.PB → ηf 2.B

(5)

(1).
(2).
(3).
(4).
(5).
(6).
(7).
(8).
(9).

Tipo 5, ηo.PB → F1, ηf 1.PB → F1, F1 = ηo.B ∪ ηf1.B
Tipo 3(b), ηf 1.PT → F2, ηf 1.PB → F2, F2 = ηo.B ∪ ηf 1.T ∪ ηf 1.B
Tipo 3(a), ηr1.PT → ηr1.T, ηr1.PB → ηr1.B
Tipo 4, ηo.PT → F3, ηr1.PT → F3, F3 = ηo.T ∪ ηr1.T, ηo.PB → ηr1.B
Tipo 5, ηo.PB → F4, ηf 2.PB → F4, F4 = ηr1.B ∪ ηf 2.B
Tipo 3(b), ηf 2.PT → F5, ηf 2.PB → F5, F5 = ηr1.B ∪ ηf 2.T ∪ ηf 2.B
Tipo 3(a), ηr2.PT → ηr2.T, ηr2.PB → ηr2.B
Tipo 4, ηo.PT → F6, ηr2.PT → F6, F6 = ηo.T ∪ ηr1.T ∪ ηr2.T, ηo.PB → ηr2.B
Tipo 3(b), ηo.PT → F7, ηo.PB → F7, F7 = ηo.T ∪ ηr1.T ∪ ηr2.T ∪ ηr2.B

Cifra 14
Multiple independent adjunction of β1 and β2 to ηo. The unifications and reassignments are
listed in the order in which they are performed during the recognition process.

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

57

Ligüística computacional

Volumen 41, Número 1

As we shall see subsequently, this correct ordering between unification and reas-
signment follows from the proposed Earley algorithm. Tipo 4 completor rules complete
the prediction triggered at the root of an auxiliary tree (“Start root of adjunction”) y
Tipo 5 completor rules complete the prediction triggered at the foot node of an auxiliary
árbol (“Start foot of adjunction”). Because completion operates bottom–up, resulta que
Tipo 5 rules apply before Type 4 normas. De este modo, when adjoining an auxiliary tree β1 to a
node ηo, the Type 5 completor rules, unifying the bottom feature structure of the foot
node of β1 with the bottom feature structure of the node ηo, occurs before the Type 4
completor rules, which reassign the bottom reference variable of ηo to the bottom feature
structure of the root of β1.

5.3.2 Inference Rules. The parsing algorithm for FB-TAG is a modification of the algorithm
presented by Schabes and Shieber (1994). It is a chart-based parsing method based on
the Earley type deduction system. Each item in the chart is of the format hN[..η] →
Γ • ∆, i, j, k, li, where N is some LIG nonterminal (es decir., t or b), and Γ and ∆ present the
sequences of LIG nonterminals associated with stacks of node indices. The indices i, j, k,
and l are markers in the input string, showing the recognized portion:5 The recognized
item starts in position i, ends in position l, and if η dominates a foot node, the tree
dominated by the foot node starts in j and ends in k. If the foot node is not dominated
by the recognized nonterminal sequence Γ, the values for j and k are taken to be the
dummy value ’−’. As in Earley algorithms, the • separates the nonterminal sequence Γ
which was parsed from the nonterminal sequence ∆ yet to be parsed.

The first three types of rules (Scanner, Predictor, and Type 1/2 Completor) son
identical to those introduced by Schabes and Shieber (1994) and do not involve any
unification operations.

The Type 3(b) completor rule enforces top and bottom unification on all nodes that
are not the root of an auxiliary tree, and the Type 3(a) completor rule prevents top and
bottom unification at the root of auxiliary trees.

The Type 4 completor rule unifies the top feature structure of the root of the auxil-
iary tree with the top feature structure of the adjunction site. Además, it ensures that
on completion of an adjunction at node η, the bottom feature structure of η is reassigned
to the bottom feature structure labeling the root of the auxiliary tree. In this way, el
unifications occurring in an independent derivation will mirror those occurring in a
dependent one in that any following adjunction will induce unifications as if it were
happening at the root node ηr of the preceding auxiliary tree (not at η).

On completion of a foot node prediction (the tree dominated by the foot of the
auxiliary tree has been recognized), the Type 5 completor rule unifies the bottom feature
structure of the foot of the auxiliary tree with the bottom feature structure of the
adjunction site.

Finalmente, the Type 6 completor unifies the top feature structure of a substitution node

with the top feature structure of the root of the tree being substituted.

r

Scanner:

hb[..η] → Γ • w∆, i, j, k, li
hb[..η] → Γw • ∆, i, j, k, yo + 1i

,

w = wl+1,

∅

5 The indices hi, j, k, li have been used in previous parsing algorithms for tree-adjoining grammars
(Vijay-Shankar and Joshi 1985; Schabes and Joshi 1988; Schabes 1991). They deliver the same
functionality here.

58

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

If w (a terminal symbol) occurs at position l+1, the scanner rule creates a new item

whose span extends to l+1.

r

Predictor:

hN[..η] → Γ • N

[µ]∆, i, j, k, li

′

hN′[µ] → •Θ, yo, −, −, li

,

∅

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Predictor rules are produced for all types of production rules. N and N

are LIG
variables taking the value t or b. Γ, ∆, and Θ are the sequences of LIG nonterminals
associated with stacks of node indices. µ is a sequence of node indices.

′

r

Tipo 1 y 2 Completor:

′
′
hb[..η] → Γ • t[η1]∆, metro, j
, k
hb[..η] → Γt[η1] • ∆, metro, j ⊕ j′, k ⊕ k′, li

ht[η1] → Θ•, i, j, k, li

, ii

,

∅,

η1 not a root node

Types 1 y 2 Completor rules permit completing Rules 1 y 2 whenever the top
of a child node is fully recognized. Aquí, t[η1] has been fully recognized as the substring
between i and l (es decir., wi+1 . . . wl). Por lo tanto, t[η1] can be completed in b[..η]. If one of t[η1]
or b[..η] dominates the foot node of the tree, the final b[..η] will have indices associated
with the substring recognized by the foot subtree. The operation ⊕ is defined as follows:

x ⊕ y = 



Tipo 3(a) Completor:

r

X,
y,
X,
undefined, de lo contrario

if y = −
if x = −
if x = y

ht[..η] → •b[..η], i, −, −, ii

hb[..η] → Θ•, i, j, k, li

ht[..η] → b[..η]•, i, j, k, li

,

∅,

η an auxiliary tree root node

The Type 3(a) Completor rule is used to complete the prediction of an auxiliary
tree rooted in η. Once the auxiliary tree dominated by b[..η] has been recognized, el
auxiliary tree itself is completely recognized. As explained earlier, there is in this case
no feature unification between the top and the bottom of the root of the auxiliary tree.

r

Tipo 3(b) Completor:

ht[..η] → •b[..η], i, −, −, ii

hb[..η] → Θ•, i, j, k, li

ht[..η] → b[..η]•, i, j, k, li

,

vale(η.PT ) ∪ val(η.PB),
η not an auxiliary tree root node

The Type 3(b) Completor rule ensures the unification of the top and bottom feature

structures for all nodes that are not the root node of an auxiliary tree.

59

Ligüística computacional

Volumen 41, Número 1

r

Tipo 4 Completor:

hb[..η] → •t[..ηηr], i, −, −, ii

ht[..ηηr] → Θ•, i, j, k, li

hb[..η] → ∆•, j, pag, q, ki

hb[..η] → t[..ηηr]•, i, pag, q, li

,

vale(η.PT) ∪ val(ηr.PT)
η.PB := ηr.PB

The auxiliary tree associated with the predicted adjunction (t[..ηηr]) at the node
η and the subtree dominated by the node η (below b[..η]) are completed, hence b[..η]
can be completely recognized with this adjunction. The associated feature unification
unifies the content of the top reference variable of the adjoining node site η with the
content of the top reference variable of the root node ηr of the adjoined auxiliary tree.
After the successful adjunction of this adjoining tree, the bottom reference variable of
the adjoining node site η is reassigned to the content of the bottom reference variable of
the root node ηr of the adjoined auxiliary tree.

r

Tipo 5 Completor:

hb[..ηηf ] → •b[..η], i, −, −, ii

hb[..η] → Θ•, i, j, k, li

hb[..ηηf ] → b[..η]•, i, i, yo, li

,

vale(η.PB) ∪ val(ηf .PB)

The foot node prediction can be completed when the adjunction has been performed
and the bottom part of the adjoining node site η has been recognized. The associated
feature unification unifies the content of the bottom reference variable of the adjoining
node site η with the content of the bottom reference variable of the foot node ηf of the
auxiliary tree being adjoined.

r

Tipo 6 Completor:

ht[η] → •t[ηr], i, −, −, ii

ht[ηr] → Θ•, i, −, −, li

ht[η] → t[ηr]•, i, −, −, li

,

vale(η.PT) ∪ val(ηr.PT)

The Type 6 Completor rule completes the substitution at the node η. The associated
feature unification unifies the content of the top reference variable of the node η with
the content of the top reference variable of the root node ηr of the initial tree.

Given these inference rules, the recognition process is initialized using axioms of the
form ht[ηs] → •Γ, 0, −, −, 0i for each rule t[ηs] → Γ where ηs is the root node of an initial
tree labeled with the start symbol. Given an input string w1 . . . wn to be recognized,
the goal items in the chart are of the form hS → t[ηs]•, 0, −, −, ni. Once at least one goal
item is found in the chart, the recognition process succeeds and the string is successfully
accepted by the grammar; otherwise it is rejected. We refer the reader to Appendix A
(cf. Figure A.2) for a detailed example of the recognition of the sentence all the meerkats
using the proposed inference system.

Note also that although the recognition algorithm we described uses unreduced
normas (es decir., generated grammar rules maintaining the full information of nonterminals
and the associated index stacks), it is possible to define a more efficient algorithm by
having reduced LIG rules and chart items listing only the single top stack element
for each constituent (Vijay-Shanker and Weir 1991, 1993). The resulting recognition

60

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

algorithm is still complete because the proposed TAG-to-LIG compilation maintains
a one-to-one correspondence between the generated rules and their reduced forms
(Schabes and Shieber 1994).

As mentioned by Schabes and Shieber (1994), this recognition algorithm can be
turned into a parsing algorithm by associating a set of operations with each chart item
to build up associated derived trees.

Note also that the derivation trees built as a side effect of the parsing process are
el (dependent and/or independent) derivation trees of an FB-LTAG and are therefore
context-free.

5.3.3 Handling Spurious Parses. As explained at the end of Section 5.2, the parsing
algorithm presented in the previous section systematically allows for dependent and
independent adjunction. Por ejemplo, the recognition of the sentence all the meerkats
(Figure A.2) produces both dependent and independent derivations that are not re-
jected by the unification constraints. En la sección 2.2, sin embargo, we argued that different
types of auxiliary trees license different types of derivations. To capture these distinc-
ciones, we modify the recognition algorithm so that it associates scopal auxiliary trees
(Ejemplo (16a–b)) with dependent derivations only and multiple intersective modifier
auxiliary trees (Ejemplo (16C)) with only an independent derivation.

(16) a. John thinks that Peter said that the meerkat left.

b. The meerkat admired the Syrian orthodox church.
C. The tall black meerkat slept.

To block dependent adjunctions between intersective modifiers, we modify the
TAG-to-LIG transformation so that, given two intersective modifier trees β1 and β2,
no Type 4 or Type 5 rule is produced.

Tipo 4: Start root of adjunction. For each elementary tree node η in tree β1 that allows the
adjunction of the auxiliary tree β2 with root node ηr, the following LIG production
rule is generated if and only if β1 and β2 are not intersective modifier auxiliary trees.

b[..η] → t[..ηηr]

vale(η.PT) ∪ val(ηr.PT)

Tipo 5: Start foot of adjunction. For each elementary tree node η that allows the adjunc-
tion of the auxiliary tree β2 with the foot node ηf , the following LIG production
rule is generated if and only if β1 and β2 are not intersective modifier auxiliary trees.

b[..ηηf ] → b[..η]

vale(η.PB) ∪ val(ηf .PB)

De este modo, por ejemplo, in the derivation of all the meerkats depicted in Appendix
Figure A.2, the following rules will not be produced, thereby blocking the production
of the dependent derivation.

b[.. NPthe
b[.. NPall

r ] → t[.. NPthe
r ] → t[.. NPall

r NPall
r ]
r NPthe
r ]

Type4

(cid:27)

b[.. NPall
b[.. NPthe

] → b[.. NPall
r NPthe
r ]
F
F ] → b[.. NPthe
r NPall
r

] )

Type5

Similarmente, to block independent adjunctions between scopal auxiliary trees, añadimos
a flag scopal? to states in the parsing algorithm. The Type 4 Completor rules associated

61

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ligüística computacional

Volumen 41, Número 1

with scopal modifiers are modified to mark the progress of a scopal adjunction and to
block the independent adjunction of another scopal modifier at the same node.

Tipo 4 Completor:

hb[..η] → •t[..ηηr], i, −, −, i, scopal?i

ht[..ηηr] → Θ•, i, j, k, yo, scopal?i

hb[..η] → ∆•, j, pag, q, k, scopal?i

hb[..η] → t[..ηηr]•, i, pag, q, yo, Truei

,

vale(η.PT) ∪ val(ηr.PT)
η.PB := ηr.PB

In the Type 4 Completor rule, once a scopal auxiliary tree β with root node ηr adjoins
at some node η, the bottom component of the node η is marked with True, recording that
a scopal adjunction has occurred at node η and that it therefore should not accept any
further scopal adjunction.

De este modo, por ejemplo, the derivation of Syrian orthodox churches will proceed in a similar
manner as the derivation of all the meerkats depicted in Appendix Figure A.2, but it will
fail to produce the chart items (40, 42, …, 52) associated with the independent adjunction.
Por lo tanto, only the dependent derivation will be produced.

Note that this modification does not block modifier adjunction above a predicative
adjunction. Por lo tanto, it successfully recognizes the sentence At what time did Brockway
say Harrison arrived?, shown in Example (15), where a wh-modifier needs to be adjoined
above a predicative adjunction. Cifra 15 shows the complete recognition algorithm
modified to rule out spurious parses in the case of multiple scopal auxiliary trees and
intersective modifier auxiliary trees.

5.3.4 Weak Generative Equivalence. The weak-generative equivalence refers to the set of
strings characterized by the formal system. A diferencia de, the strong-generative equiva-
lence relates to the set of structural descriptions (such as derivation trees, dags, proof
árboles, etc.) assigned by a formal system to the strings that it specifies (Vijay-Shankar and
Joshi 1985; Joshi 2000).

Using an argument similar to that put forward by Schabes and Shieber (1994),
we can prove the weak-generative equivalence of TAGs under the dependent and our
independent derivations. We call the set of languages generated by the standard deriva-
tion in TAG, TALstd; the set of languages generated by Schabes and Shieber’s extended
derivation in TAG, TALextss ; the set of languages generated with our modifications for
FB-TAG, TALext; and the set of languages generated by the LIG, LIL. Our derivation
allows both dependent and independent derivations; por lo tanto, our derivation will
recognize all the strings recognized by the standard (dependent) derivation. Más
precisamente, our derivation can mimic the standard derivation by not allowing more than
one adjunction on a tree node by treating all auxiliary trees as scopal auxiliary trees
(cf. Sección 5.3.3), henceforth, TALstd ⊆ TALext. The proposed compilation from TAGs
to LIGs for the independent derivation concluded TALext ⊆ LIL. Finalmente, LIL ⊆ TALstd
has been proven by Vijay-Shanker (1987). Combining these three inclusions, podemos
conclude that TALstd = TALext. Además, Schabes and Shieber (1994) have shown
that TALstd = TALextss . Por eso, we can conclude the weak-generative equivalence of all
three derivations in TAGs, TALstd = TALextss
= TALext. Feature structures enhance TAGs’
descriptive ability without affecting their generative capacity (Vijay-Shanker and Joshi
1988). The proposed algorithm simulates the established unification mechanism in FB-
TAG without affecting the representation and the stipulations (p.ej., null adjunction at

62

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

r

r

r

r

r

r

r

r

Scanner:

Predictor:

hb[..η] → Γ • w∆, i, j, k, yo, S?i
hb[..η] → Γw • ∆, i, j, k, yo + 1, S?i

,

w = wl+1,

∅

hP[..η] → Γ • P

′

[µ]∆, i, j, k, yo, −i

hP′

[µ] → •Θ, yo, −, −, yo, S?i

,

∅

Tipo 1 y 2 Completor:

′
hb[..η] → Γ • t[η1]∆, metro, j
hb[..η] → Γt[η1] • ∆, metro, j ⊕ j′

, i, S?i

′
, k

ht[η1] → Θ•, i, j, k, yo, −i
, k ⊕ k′
, yo, S?i

,

∅,

η1 not a root node

Tipo 3(a) Completor:

ht[..η] → •b[..η], i, −, −, i, −i

hb[..η] → Θ•, i, j, k, yo, S?i

ht[..η] → b[..η]•, i, j, k, yo, S?i

,

∅,

η an auxiliary tree root node

Tipo 3(b) Completor:

ht[..η] → •b[..η], i, −, −, i, −i

hb[..η] → Θ•, i, j, k, yo, S?i

ht[..η] → b[..η]•, i, j, k, yo, S?i

,

vale(η.PT ) ∪ val(η.PB ),

η not an auxiliary tree root node

Tipo 4 Completor:

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

hb[..η] → •t[..ηηscopal

r

], i, −, −, i, −i

ht[..ηηscopal
r

] → Θ•, i, j, k, yo, −i

hb[..η] → ∆•, j, pag, q, k, S?i

hb[..η] → t[..ηηscopal

r

]•, i, pag, q, yo, Truei

hb[..η] → •t[..ηηothers

r

], i, −, −, i, −i

ht[..ηηothers
r

] → Θ•, i, j, k, yo, −i

hb[..η] → t[..ηηothers

r

hb[..η] → ∆•, j, pag, q, k, S?i
]•, i, pag, q, yo, S?i

,

,

vale(η.PT ) ∪ val(ηscopal

r

.PT )

η.PB := ηscopal

r

.PBr

vale(η.PT ) ∪ val(ηothers

r

.PT )

η.PB := ηothers

r

.PBr

Tipo 5 Completor:

hb[..ηηscopal
F

] → •b[..η], i, −, −, i, S?i

hb[..η] → Θ•, i, j, k, yo, S1?i

hb[..ηηscopal
F

] → b[..η]•, i, i, yo, yo, S?i

vale(η.PB ) ∪ val(ηscopal

F

.PBf )

,

S1? 6= True

hb[..ηηothers
F

] → •b[..η], i, −, −, i, S?i

hb[..η] → Θ•, i, j, k, yo, −i

hb[..ηηothers

F

] → b[..η]•, i, i, yo, yo, S?i

,

vale(η.PB ) ∪ val(ηothers

F

.PBf

)

Tipo 6 Completor:

ht[η] → •t[ηr], i, −, −, i, S?i

ht[ηr] → Θ•, i, −, −, yo, −i

ht[η] → t[ηr]•, i, −, −, yo, S?i

,

vale(η.PT ) ∪ val(ηr.PTr )

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

63

Cifra 15
Recognition algorithm taking into account spurious parses.

Ligüística computacional

Volumen 41, Número 1

the foot node and the bounded feature structures) of the grammar itself. Por lo tanto,
the association with feature structures will not affect this equivalence.

6. Conclusión

Although independent derivations have been shown by Schabes and Shieber (1994)
to be essential for correctly supporting syntactic analysis, semantic interpretation, y
statistical language modeling, the parsing algorithm they propose is restricted to TAG
and is therefore not directly applicable to large scale implemented Feature-Based TAGs.
We have provided a recognition algorithm for FB-TAGs that supports both dependent
and independent derivations under certain restrictions enforced jointly by feature con-
straints and by side conditions in the parsing algorithm. The resulting algorithm com-
bines the benefits of independent derivations with those of Feature-Based Grammars.
En particular, we showed that it accounts for a range of interactions between dependent
vs. independent derivation on the one hand, and syntactic constraints, linear ordering,
and scopal vs. nonscopal semantic dependencies on the other hand.

Apéndice A: Recognition of the String all the meerkats

We show the recognition of the string all the meerkats as per the inference rules described
en la sección 5.3.2.

Figure A.1 shows the grammar used for the derivation. To support multiple adjunc-
tion in FB-TAG, it implements two main modifications. Primero, to facilitate the TAG to
LIG compilation, each tree node in the grammar is marked with a unique identifier. Para
, Detthe, NPthe
ejemplo, in Figure A.1, NPmk, NPthe
F * are unique
node identifiers in the grammar. Segundo, to implement the reassignment mechanism in

r , Detall, and NPthe

F *, NPall

r

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

NPmk P

Tmk

PAG

Bmk

→[Tmk:[]]
→[Bmk:[]]

meerkat

αmeerkat

NPthe
r

PAG

Tthe
r

PAG

Bthe
r

r

→[Tthe
→[Bthe

r

:[]]
:[det:el]]

Detthe

→[Tthe
→[Bthe

det:[]]
det:[]]

PAG

Tthe
det

PAG

Bthe
det

NPthe
F *

PAG

Tthe
F

PAG

Bthe
F

→

Tthe
F

:[det:nil]

i

→

h
Bthe
F

:[]

h

i

el

NPall
r

PAG

Tall
r

PAG

Ball
r

βthe

→[Tall
→[Ball

r :[]]
r :[det:todo]]

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

→

→

Tall
F
h
Ball
F
h

:[]

i

:[]

i

Detall

→[Tall
→[Ball

det:[]]
det:[]]

PAG

Tall
det

PAG

Ball
det

NPall
F *

PAG

Tall
F

PAG

Ball
F

todo

βall

Figure A.1
A feature-based Tree-Adjoining Grammar.

64

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

Tipo 1 and Type 2 production rules

Tipo 3(b) production rules (continued)

b[NPmk] → meerkat

b[.. NPthe

r

] → t[Detthe]

t[.. NPthe

F

]

t[.. Detall] → b[.. Detall]

t[.. NPall

F ] → b[.. NPall
F ]

b[Detthe] → the

Tipo 4 production rules

b[.. NPall

r ] → t[Detall]

t[.. NPall
F ]

b[Detall] → all

Tipo 3(a) production rules

t[.. NPthe

r

] → b[.. NPthe

r

]

t[.. NPall

r ] → b[.. NPall
r ]

b[.. NPmk] → t[.. NPmk NPthe

r

]

b[.. NPmk] → t[.. NPmk NPall
r ]

b[.. NPthe

r

] → t[.. NPthe

r NPall
r ]

b[.. NPall

r ] → t[.. NPall

r NPthe
r

]

Tipo 5 production rules

Tipo 3(b) production rules

b[.. NPmk NPthe

F

] → b[.. NPmk]

t[.. NPmk] → b[.. NPmk]

t[.. Detthe] → b[.. Detthe]

t[.. NPthe

F

] → b[.. NPthe

F

]

Figure A.2
LIG production rules for the TAG shown in Figure A.1.

b[.. NPall

r NPthe

F

] → b[.. NPall
r ]

b[.. NPmk NPall

F ] → b[.. NPmk]

b[.. NPthe

r NPall

F ] → b[.. NPthe
r

]

the parsing algorithm, the top (t) and the bottom (B) feature structures of each node are
assigned reference variables PT and PB, respectivamente.

Figure A.2 shows the LIG production rules for the FB-TAG shown in Figure A.1.
Table A.1 shows the step-wise recognition of the string all the meerkats. Recall Sec-
ción 5.3.2: The LIG rules shown in Figure A.1 does not deal with spurious parses and
produces all valid derivations, dependent or independent, that are not blocked by fea-
ture unification constraints. Por eso, for the string all the meerkats, it generates both inde-
pendiente (Step 52) and dependent (Step 53) derivations. As explained in Figures A.3 and
A.4, both derivations undergo the identical set of feature unifications. In both figures,
prediction rules are abbreviated because they do not enforce any feature unification.

Cuadro A.1
Recognition of the string 0 todo 1 el 2 meerkats 3 in FB-TAG.

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

#

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

Chart Items

Descripción

r ], 0, −, −, 0i
r ], 0, −, −, 0i

hS → •t[NPmk], 0, −, −, 0i
ht[NPmk] → •b[NPmk], 0, −, −, 0i
hb[NPmk] → •t[NPmk NPthe
hb[NPmk] → •t[NPmk NPall
r ] → •b[NPmk NPthe
ht[NPmk NPthe
r ] → •b[NPmk NPall
ht[NPmk NPall
r ] → •t[NPmk NPthe
hb[NPmk NPthe
r ] → •t[Detall] t[NPmk NPall
hb[NPmk NPall
ht[NPmk NPthe
r NPall
ht[Detall] → •b[Detall], 0, −, −, 0i

r ] → •b[NPmk NPthe

r ], 0, −, −, 0i
r ], 0, −, −, 0i
r NPall

r ], 0, −, −, 0i

F ], 0, −, −, 0i

r NPall

r ], 0, −, −, 0i

axiom
3(b)-pred, 1
4-pred, 2
4-pred, 2
3(a)-pred, 3
3(a)-pred, 4
4-pred, 5
1/2-pred, 6
3(a)-pred, 7
3(b)-pred, 8

65

Ligüística computacional

Volumen 41, Número 1

Cuadro A.1
(continued)

r ] → •t[Detall] t[NPmk NPthe

r NPall

F ], 0, −, −, 0i

r ] → t[Detall] • t[NPmk NPthe

F ], 0, −, −, 1i

F ], 0, −, −, 1i
r NPall

Chart Items

F

F

r NPall

r ] → t[Detthe] • t[NPmk NPthe
F
F

] → •b[NPmk NPthe
] → •b[NPmk], 2, −, −, 2i

r ] → t[Detall] • t[NPmk NPall
r NPall
F ] → •b[NPmk NPall
F ] → •b[NPmk NPthe
r NPall
F ] → •b[NPmk], 1, −, −, 1i
F ] → •b[NPmk NPthe
r NPall
r ], 1, −, −, 1i

hb[NPmk NPthe
hb[Detall] → •all, 0, −, −, 0i
hb[Detall] → all•, 0, −, −, 1i
ht[Detall] → b[Detall]•, 0, −, −, 1i
hb[NPmk NPall
hb[NPmk NPthe
ht[NPmk NPall
ht[NPmk NPthe
hb[NPmk NPall
hb[NPmk NPthe
hb[NPmk] → •t[NPmk NPthe
r ] → •t[Detthe] t[NPmk NPthe
hb[NPmk NPthe
F
ht[NPmk NPthe
r ] → •b[NPmk NPthe
ht[Detthe] → •b[Detthe], 1, −, −, 1i
hb[Detall] → •the, 1, −, −, 1i
hb[Detthe] → the•, 1, −, −, 2i
ht[Detthe] → b[Detthe]•, 1, −, −, 2i
hb[NPmk NPthe
ht[NPmk NPthe
hb[NPmk NPthe
hb[NPmk] → •meerkat, 2, −, −, 2i
hb[NPmk] → meerkat•, 2, −, −, 3i
hb[NPmk NPthe
F
ht[NPmk NPthe
hb[NPmk NPthe
ht[NPmk NPthe
hb[NPmk NPthe
hb[NPmk] → t[NPmk NPthe
ht[NPmk NPthe
hb[NPmk NPall
hb[NPmk NPthe
ht[NPmk NPall
ht[NPmk NPthe
hb[NPmk NPall
hb[NPmk NPthe
ht[NPmk NPall
ht[NPmk NPthe
hb[NPmk] → t[NPmk NPall
hb[NPmk] → t[NPmk NPthe
ht[NPmk] → b[NPmk]•, 0, −, −, 3i
ht[NPmk] → b[NPmk]•, 0, −, −, 3i
hS → t[NPmk]•, 0, −, −, 3i
hS → t[NPmk]•, 0, −, −, 3i

F ] → b[NPmk NPthe
r ]•, 1, −, −, 3i
F ] → b[NPmk NPthe
r NPall
F ] → b[NPmk]•, 1, 1, 3, 3i
r NPall
F ] → b[NPmk NPall
r NPall
r ] → t[Detall] t[NPmk NPall
r ] → t[NPmk NPthe
r ] → b[NPmk NPall
r ] → b[NPmk NPthe

F
r ] → t[Detthe] t[NPmk NPthe
F
r ] → b[NPmk NPthe
r NPall

] → b[NPmk]•, 2, 2, 3, 3i
] → b[NPmk NPthe

r ]•, 0, −, −, 3i
r ]•, 0, −, −, 3i

r ] → b[NPmk NPthe

r NPall
r ]•, 0, 1, 3, 3i
r ]•, 0, 2, 3, 3i

F ]•, 1, 1, 3, 3i
r NPall

r ]•, 1, 2, 3, 3i

]•, 2, 2, 3, 3i

r NPall

F

F ], 1, −, −, 1i
r NPall

F ], 1, −, −, 1i

r ], 1, −, −, 1i

], 1, −, −, 1i

r ], 1, −, −, 1i

], 1, −, −, 2i

], 2, −, −, 2i

]•, 1, 2, 3, 3i

r ]•, 1, 1, 3, 3i

F ]•, 1, 1, 3, 3i

r ]•, 0, 1, 3, 3i

F ]•, 0, 1, 3, 3i

r ]•, 0, 2, 3, 3i

r ] → t[Detall] t[NPmk NPthe

r NPall

F ]•, 0, 1, 3, 3i

Descripción

1/2-pred, 9
1/2-pred, 10
scan, 12
3(b)-comp, (10, 13)
1/2-comp, (8, 14)
1/2-comp, (11, 14)
3(b)-pred, 15
3(b)-pred, 16
5-pred, 17
5-pred, 18
4-pred, 19
1/2-pred, 20
3(a)-pred, 21
3(b)-pred, 22
1/2-pred, 24
scan, 25
3(b)-comp, (24, 26)
1/2-comp, (22, 27)
3(b)-pred, 28
5-pred, 29
1/2-pred, 30
scan, 31
5-comp, (30, 32)
3(b)-comp, (29, 33)
1/2-comp, (28, 34)
3(a)-comp, (23, 35)
5-comp, (20, 35)
4-comp, (21, 36, 32)
3(b)-comp, (18, 37)
5-comp, (19, 38)
1/2-comp, (16, 39)
3(b)-comp, (17, 40)
3(a)-comp, (9, 41)
1/2-comp, (15, 42)
4-comp, (7, 43, 35)
3(a)-comp, (6, 44)
3(a)-comp, (5, 45)
4-comp, (4, 46, 38)
4-comp, (3, 47, 32)
3(b)-comp, (2, 48)
3(b)-comp, (2, 49)
axiom-comp, (1, 50)
axiom-comp, (1, 51)

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

#

11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.

66

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Figure A.3
Feature unifications in dependent derivation of all the meerkats (prediction rules are abbreviated).

67

Ligüística computacional

Volumen 41, Número 1

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Figure A.4
Feature unifications in independent derivation of all the meerkats (prediction rules are
abbreviated).

68

Gardent and Narayan

Multiple Adjunction in Feature-Based Tree Adjoining Grammar

Expresiones de gratitud
We would like to thank Laura
Perez-Beltrachini for useful discussion on
the related topic. We are grateful to our
anonymous reviewers for their insightful
comments, which helped us improve
the quality of the article in terms of both
presentation and content.

Referencias
Alahverdzhieva, Katya. 2008. XTAG

using XMG. Tesis de maestría, Universit´e
de Nancy.

Candito, Marie-H´el`ene and Sylvain Kahane.

1998. Can the TAG derivation tree
represent a semantic graph? An answer
in the light of Meaning-Text Theory.
In Proceedings of the Fourth Workshop
on Tree-Adjoining Grammars and Related
Frameworks (TAG+4), pages 21–24,
Filadelfia, Pensilvania.

Crabb´e, Benoˆıt, Denys Duchier, Claire

Gardent, Joseph Le Roux, and Yannick
Parmentier. 2013. XMG: eXtensible
MetaGrammar. Ligüística computacional,
39(3):1–66.

Gardent, Claire. 2008. Integrating a

unification-based semantics in a large
scale Lexicalised Tree Adjoining
Grammar for French. En procedimientos de
the 22nd International Conference on
Ligüística computacional (COLECCIONAR),
pages 249–256, Manchester.

Gardent, Claire and Laura Kallmeyer. 2003.
Semantic construction in Feature-Based
TAG. In Proceedings of the 10th Conference
of the European Chapter of the Association
para Lingüística Computacional (EACL),
pages 123–130, Budapest.

Gazdar, Gerald. 1988. Applicability of

indexed grammars to natural languages.
In Uwe Reyle and Christian Rohrer,
editores, Natural Language Parsing and
Linguistic Theories, volumen 35 of Studies
in Linguistics and Philosophy. Saltador,
Países Bajos, pages 69–94.

Joshi, Aravind K. 2000. Relationship between

strong and weak generative power of
formal systems. En Actas de la
5th International Workshop on Tree Adjoining
Grammars and Related Formalisms (TAG+5),
pages 107–114, París.

Joshi, Aravind K. and Yves Schabes. 1997.
Tree-Adjoining Grammars. Handbook of
Formal Languages and Automata, 3:69–124.
Joshi, Aravind K. and K. Vijay-Shanker. 2001.
Compositional semantics with lexicalized
tree-adjoining grammar (LTAG): Cómo

much underspecification is necessary?
In Harry Bunt, Reinhard Muskens, y
Elias Thijsse, editores, Computing Meaning,
volumen 77 of Studies in Linguistics and
Philosophy. Saltador, Países Bajos,
pages 147–163.

Kallmeyer, Laura and Marco Kuhlmann.
2012. A formal model for plausible
dependencies in lexicalized tree
adjoining grammar. En procedimientos de
the 11th International Workshop on
Tree Adjoining Grammars and Related
Formalisms (TAG+11), pages 108–116,
París.

Kroch, Antonio. 1989. Asymmetries in long
distance extraction in a tree adjoining
gramática. En m. Baltin and A. Kroch,
editores, Alternative conceptions of phrase
estructura, University of Chicago Press,
pages 66–98.

Rambow, Owen, k. Vijay-Shanker, y

David Weir. 1995. D-Tree Grammars. En
Proceedings of the 33rd Annual Meeting of
la Asociación de Lingüística Computacional
(LCA), pages 151–158, Cambridge, MAMÁ.

Resnik, Philip. 1992. probabilístico

tree-adjoining grammar as a framework
for statistical natural language processing.
In Proceedings of the 14th Conference
on Computational linguistics (COLECCIONAR),
volumen 2, pages 418–424, Nantes.
Schabes, Yves. 1991. The valid prefix

property and left to right parsing of
tree-adjoining grammar. En procedimientos de
the 2nd International Workshop on Parsing
Technologies (IWPT), pages 21–30, Cancun.

Schabes, Yves. 1992. Stochastic lexicalized
tree-adjoining grammars. En procedimientos
of the 14th Conference on Computational
Lingüística (COLECCIONAR), volumen 2,
pages 425–432, Nantes.

Schabes, Yves and Aravind K. Joshi. 1988.
An Earley-type parsing algorithm for
tree adjoining grammars. En procedimientos de
the 26th Annual Meeting of the Association
para Lingüística Computacional (LCA),
pages 258–269, Buffalo, Nueva York.

Schabes, Yves and Stuart M. Shieber. 1992.

An alternative conception of tree-adjoining
derivation. In Proceedings of the 30th Annual
Meeting of the Association for Computational
Lingüística (LCA), pages 167–176,
Nueva York, DE.

Schabes, Yves and Stuart M. Shieber. 1994.

An alternative conception of tree-adjoining
derivation. Ligüística computacional,
20(1):91–124.

Shieber, Stuart M. 1994. Restricting the

weak-generative capacity of synchronous

69

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
/
C
oh

yo
i
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

/

/

/

4
1
1
4
1
1
8
0
6
0
0
0
/
C
oh

yo
i

_
a
_
0
0
2
1
7
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ligüística computacional

Volumen 41, Número 1

tree-adjoining grammars. computacional
Inteligencia, 10(4):371–385.

Steedman, Marca. 2000. The syntactic process.