Lexicalization and Generative Power in CCG

Marco Kuhlmann∗
Link ¨oping University

Alejandro Koller
University of Potsdam

∗∗

†

Giorgio Satta
University of Padua

The weak equivalence of Combinatory Categorial Grammar (CCG) and Tree-Adjoining Gram-
mar (TAG) is a central result of the literature on mildly context-sensitive grammar formalisms.
Sin embargo, the categorial formalism for which this equivalence has been established differs sig-
niﬁcantly from the versions of CCG that are in use today. En particular, it allows restriction
of combinatory rules on a per grammar basis, whereas modern CCG assumes a universal set
of rules, isolating all cross-linguistic variation in the lexicon. In this article we investigate the
formal signiﬁcance of this difference. Our main result is that lexicalized versions of the classical
CCG formalism are strictly less powerful than TAG.

1. Introducción

Since the late 1970s, several grammar formalisms have been proposed that extend the
power of context-free grammars in restricted ways. The two most prominent members
of this class of “mildly context-sensitive” formalisms (a term coined by Joshi 1985) son
Tree-Adjoining Grammar (TAG; Joshi and Schabes 1997) and Combinatory Categorial
Grammar (CCG; Steedman 2000; Steedman and Baldridge 2011). Both formalisms have
been applied to a broad range of linguistic phenomena, and are being widely used in
computational linguistics and natural language processing.

In a seminal paper, Vijay-Shanker and Weir (1994) showed that TAG, CCG, and two
other mildly context-sensitive formalisms—Head Grammar (Pollard 1984) and Linear
Indexed Grammar (Gazdar 1987)—all characterize the same class of string languages.
Sin embargo, when citing this result it is sometimes overlooked that the result applies to a
version of CCG that is quite different from the versions that are in practical use today.

∗ Department of Computer and Information Science, Link ¨oping University, 581 83 Link ¨oping, Suecia.

Correo electrónico: marco.kuhlmann@liu.se.

∗∗ Department of Linguistics, Karl-Liebknecht-Str. 24–25, University of Potsdam, 14476 Potsdam, Alemania.

Correo electrónico: koller@ling.uni-potsdam.de.

† Department of Information Engineering, University of Padua, via Gradenigo 6/A, 35131 Padova, Italia.

Correo electrónico: satta@dei.unipd.it.

Envío recibido: 4 December 2013; revised submission received: 26 Julio 2014; accepted for publication:
25 Noviembre 2014.

doi:10.1162/COLI a 00219

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Ligüística computacional

Volumen 41, Número 2

The goal of this article is to contribute to a better understanding of the signiﬁcance of
this difference.

The difference between “classical” CCG as formalized by Vijay-Shanker and Weir
(1994) and the modern perspective may be illustrated with the combinatory rule of
backward-crossed composition. The general form of this rule looks as follows:

Backward-crossed composition, general form:
Y/Z X/Y ⇒ X/Z

(

< Figure 3 A sample derivation (adapted from Steedman 2012). 218 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . e d u / c o l i / l a r t i c e - p d f / / / / 4 1 2 2 1 5 1 8 0 4 9 4 7 / c o l i _ a _ 0 0 2 1 9 p d . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Kuhlmann, Koller, and Satta Lexicalization and Generative Power in CCG 2. if X, Y ∈ C(A) then X/Y ∈ C(A) and X/Y ∈ C(A). We use the letters A, B, C to denote atomic categories, the letters X, Y, Z to denote arbitrary categories, and the symbol | to denote slashes (forward or backward). We treat slashes as left-associative operators and omit unnecessary parentheses. By this convention, every category X can be written in the form X = A| mXm · · · | 1X1 where m ≥ 0, A is an atomic category that we call the target of X, and the | iXi are slash–category pairs that we call the arguments of X. Intuitively, the target of X is the atomic category that is obtained after X has been applied to all of its arguments. We use the Greek letters α, β, γ to denote (potentially empty) sequences of arguments. The number m is called the arity of the category X. Rules. Categories can combine under a number of rules; this gives rise to derivations such as the one shown in Figure 3. Each rule speciﬁes an operation that assembles two input categories into an output category. The two most basic rules of CCG are the directed versions of function application: X/Y Y ⇒ X Y X/Y ⇒ X (forward application) (backward application) (>)
(<) Formally, a rule is a syntactic object in which the letters X, Y, Z act as variables for cat- egories. A rule instance is obtained by substituting concrete categories for all variables in the rule. For example, the derivation in Figure 3 contains the following instances of function application. We denote rule instances by using a triple arrow instead of the double arrow in our notation for rules. (S/NP)/NP NP (cid:2) S/NP and NP S/NP (cid:2) S Application rules give rise to derivations equivalent to those of context-free gram- mar. Indeed, versions of categorial grammar where application is the only mode of combination, such as AB-grammar (Ajdukiewicz 1935; Bar-Hillel, Gaifman, and Shamir 1960), can only generate context-free languages. CCG can be more powerful because it also includes other rules, derived from the combinators of combinatory logic (Curry, Feys, and Craig 1958). In this article, as in most of the formal work on CCG, we restrict our attention to the rules of (generalized) composition, which are based on the B combinator.1 The general form of composition rules is shown in Figure 4. In each rule, the two input categories are distinguished into one primary (shaded) and one secondary input category. The number n of outermost arguments of the secondary input category is called the degree of the rule.2 In particular, for n = 0 we obtain the rules of function 1 This means that we ignore other rules required for linguistic analysis, in particular type-raising (from the T combinator), substitution (from the S combinator), and coordination. 2 The literature on CCG assumes a bound on n; for English, Steedman (2000, p. 42) puts n ≤ 3. Adding rules of unbounded degree increases the generative capacity of the formalism (Weir and Joshi 1988). 219 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . e d u / c o l i / l a r t i c e - p d f / / / / 4 1 2 2 1 5 1 8 0 4 9 4 7 / c o l i _ a _ 0 0 2 1 9 p d . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Computational Linguistics Volume 41, Number 2 Figure 4 General form of composition rules (primary input category shaded), where n ≥ 0 and | i ∈ {/, /}. Figure 5 Schematic deﬁnition of the set of derivation trees of a grammar G. application. In contexts where we refer to both application and composition, we use the latter term for composition rules with degree n > 0.

Derivation Trees. Derivation trees can now be schematically deﬁned as in Figure 5. Ellos
contain two types of branchings: unary branchings correspond to lexicon entries; binario
branchings correspond to rule instances. The yield of a derivation tree is the left-to-right
concatenation of its leaves.

2.2 Classical CCG

We now deﬁne the classical CCG formalism that was studied by Vijay-Shanker and Weir
(1994) and originally introduced by Weir and Joshi (1988). As mentioned in Section 1, el
central feature of this formalism is its ability to impose restrictions on the applicability
of combinatory rules. Específicamente, a restricted rule is a rule annotated with constraints
eso

(a)

(b)

restrict the target of the primary input category; and/or

restrict the secondary input category, either in parts or in its entirety.

Every grammar lists a ﬁnite number of restricted rules (where one and the same base
rule may occur with several different restrictions). A valid rule instance is an instance
that is compatible with at least one of the restricted rules.

Ejemplo 1
Linguistic grammars make frequent use of rule restrictions. To exclude the undesired
derivation in Figure 1 we restricted backward crossed composition to instances where
both the primary and the secondary input category are functions into the category of

220

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

oraciones, S. Writing target for the function that returns the target of a category, el
restricted rule can be written as

Y/Z X/Y ⇒ X/Z
where target(X) = S and target(Y) = S

(backward crossed composition)

(2) where the target of the primary
input category is S and the secondary input category is B/C/B.

Note that every VW-CCG can be speciﬁed using a ﬁnite set of templates: It has a
ﬁnite set of combinatory rules; the set of possible targets of the primary input category
of each rule is ﬁnite because each target is an atomic category; and the set of possible
secondary input categories is ﬁnite because of Lemma 2.

223

Ligüística computacional

Volumen 41, Número 2

2.3 Tree-Adjoining Grammar

In this article we are interested in the generative power of CCG, in particular in its re-
lation to that of Tree-Adjoining Grammar. We therefore provide a compact introduction
to TAG. For more details, we refer to Joshi and Schabes (1997).

Elementary Trees. Tree-Adjoining Grammar is a formalism for generating trees. Estos
trees can be characterized as rooted, ordered trees in which internal nodes are labeled
with nonterminal symbols—including a distinguished start symbol S—and leaf nodes
are labeled with nonterminals, terminals, or the empty string. Every grammar speciﬁes
a ﬁnite set of such trees; these are called elementary trees. There are two types: ini-
tial trees and auxiliary trees. They differ in that auxiliary trees have a distinguished
nonterminal-labeled leaf node, called foot node; this node is conventionally marked
with an asterisk. An elementary tree whose root node is labeled with a nonterminal A
is called an A-tree.

Substitution and Adjunction. New trees may be derived by combining other trees using
two operations called substitution and adjunction. Substitution replaces some leaf
node of a given tree with an initial tree (or a tree derived from an initial tree). Adjunction
replaces some internal node u of a given tree with an auxiliary tree (or a tree derived
from an auxiliary tree); the subtree with root u replaces the foot node of the auxiliary
árbol. All replacements are subject to the condition that the node being replaced and the
root of the tree that replaces it are labeled with the same nonterminal.

Generated Languages. The tree language generated by a TAG is the set of all trees that
can be derived from its initial S-trees. Derivations are considered complete only if they
satisfy additional, node-speciﬁc constraints. En particular, substitution is obligatory at
every node where it is possible, and adjunction may be speciﬁed as either obligatory
(OA, Obligatory Adjunction) or forbidden (NA, Null Adjunction) at a given node. En
derived trees corresponding to complete derivations, all leaf nodes are labeled with
terminal symbols. The left-to-right concatenation of these symbols forms the yield of the
árbol, and the yields of all trees in the tree language form the string language generated
by the TAG.

Ejemplo 5
= {anbncn | n ≥ 1} deﬁned in
Cifra 8 shows a TAG that generates the language L1
Ejemplo 2. Derivations start with adjoining the auxiliary tree t2 at the root of the initial
tree t1. New trees can be derived by repeatedly adjoining t2 at an S-node.

Cifra 8
A TAG that generates the language L1

= {anbncn | n ≥ 1}.

224

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

2.4 Generative Capacity of Classical CCG

Vijay-Shanker and Weir (1994) proved the following:

Teorema 1
VW-CCG and TAG are weakly equivalent.

The inclusion of the VW-CCG languages in the TAG languages follows from a
chain of inclusions that connects VW-CCG and TAG via Linear Indexed Grammar (LIG;
Gazdar 1987) and Head Grammar (HG; Pollard 1984). All of these inclusions were
proved by Vijay-Shanker and Weir (1994). Here we sketch a proof of the inclusion of
the TAG languages in the VW-CCG languages. Our proof closely follows that of Weir
(1988, Sección 5.2.2), whose construction we shall return to when establishing our own
resultados.

Lema 3
The TAG languages are included in the VW-CCG languages.

Prueba (Sketch)
We are given a TAG G and construct a weakly equivalent VW-CCG G
. The basic idea is
(cid:2)
correspond to the elementary trees of G, and to set
to make the lexical categories of G
(cid:2)
up the combinatory rules and their restrictions in such a way that the derivations of G
correspond to derivations of G.

(cid:2)

Vocabulary, Atomic Categories. The vocabulary of G
is the set of all terminal symbols
of G; the set of atomic categories consists of all symbols of the form At, where ei-
ther A is a nonterminal symbol of G and t ∈ {a, C}, or A is a terminal symbol of G
and t = a. The distinguished atomic category of G
is Sa, where S is the start symbol
of G.

(cid:2)

Lexicon. One may assume (cf. Vijay-Shanker, Weir, and Joshi 1986) that G is in the normal
form shown in Figure 9. In this normal form there is a single initial S-tree, and all
remaining elementary trees are auxiliary trees of one of ﬁve possible types. For each
such tree, one constructs two lexicon entries for the empty string ε as speciﬁed in
Cifra 9. Además, for each terminal symbol x of G, one constructs a lexicon entry
X := xa.

(cid:2)

Rules. The rules of G
are forward and backward application and forward and backward
composition of degree at most 2. They are used to simulate adjunction operations
in derivations of G: Application simulates adjunction into nodes to the left or right
of the foot node; composition simulates adjunction into nodes above the foot node.
Without restrictions, these rules would allow derivations that do not correspond to
derivations of G. Por lo tanto, rules are restricted such that an argument of the form
|At can be eliminated by means of an application rule only if t = a, and by means of
a composition rule only if t = c. This enforces two properties that are central for the
correctness of the construction (Weir 1988, pag. 119): Primero, the secondary input category
in every instance of composition is a category that has just been introduced from the

225

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Ligüística computacional

Volumen 41, Número 2

Cifra 9
Correspondence between elementary trees and lexical categories in the proof of Lemma 3.

lexicon. Segundo, categories cannot be combined in arbitrary orders. The rule restric-
tions are:

Forward and backward application are restricted to instances where both
the target of the primary input category and the entire secondary input
category take the form Aa.

Forward and backward composition are restricted to instances where the
target of the primary input category takes the form Aa and the target of the
secondary input category takes the form Ac.

Using our template notation, the restricted rules can be written as in Figure 10. (cid:3)

As an aside we note that the proof of Lemma 3 makes heavy use of the ability
of VW-CCG to assign lexicon entries to the empty string. Such lexicon entries violate
one of the central linguistic principles of CCG, the Principle of Adjacency, according to
which combinatory rules may only apply to phonologically realized entities (Steedman
2000, pag. 54). It is an interesting question for future research whether a version of
VW-CCG without lexicon entries for the empty string remains weakly equivalent to
TAG.

226

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

Cifra 10
Restricted rules used in the proof of Lemma 3. We write V for the union of the nonterminal
symbols and terminal symbols of the TAG G, and let V t = {En | A ∈ V}, t ∈ {a, C}.

3. Relevance of Target Restrictions in Preﬁx-Closed CCG

In this section we present the central technical results of this article. We study a class of
VW-CCGs that we call preﬁx-closed and show that for this class, weak equivalence with
TAG stands and falls with the ability to specify target restrictions.

3.1 Preﬁx-Closed Grammars

Rule restrictions are important tools in grammars for natural language; but not all of
their potential uses have obvious linguistic motivations. Por ejemplo, one could write a
grammar that permits all compositions with a functional category A/B as the secondary
input category, but rules out application with the “shorter” category A. Such constraints
do not seem to be used in linguistically motivated grammars; Por ejemplo, none of the
grammars developed by Steedman (2000) needs them. In preﬁx-closed grammars, este
use of rule restrictions is explicitly barred.

Definición 2
A VW-CCG is preﬁx-closed if it satisﬁes the following implication:

then so is

X/Y Y|
X/Y Y|

nYn

· · · |

1Y1

nYn

· · · |

kYk

(cid:2) X|
(cid:2) X|

nYn

· · · |

1Y1

kYk

is a valid rule instance
for any k ≥ 1

and similarly for backward rules.

Note that preﬁx-closed grammars still allow some types of rule restrictions. El
crucial property is that, if a certain combinatory rule applies at all, then it also applies
to combinations where the secondary input category has already been applied to some
(k ≤ n) or even all (k > n) of its arguments.

Ejemplo 6
We illustrate preﬁx-closedness using some examples:

Every AB-grammar (when seen as a VW-CCG) is trivially preﬁx-closed; en
these grammars, norte = 0.

The “pure” grammars that we considered in our earlier work (Kuhlmann,
Koller, and Satta 2010) are trivially preﬁx-closed.

227

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Ligüística computacional

Volumen 41, Número 2

The grammar G1 from Example 2 is preﬁx-closed.

The grammars constructed in the proof of Lemma 3 are not preﬁx-closed;
they do not allow the following instances of application, donde el
secondary input category is of the form Bc (rather than Ba):

Aa (cid:4) /Bc Bc (cid:2) Aa (cid:4)
Bc Aa (cid:4) /Bc (cid:2) Aa (cid:4)

dónde

A, B ∈ V
A, B ∈ V

Ejemplo 7
The linguistic intuition underlying preﬁx-closed grammars is that if such a grammar
allows us to delay the combination of a functor and its argument (via composition),
then it also allows us to combine the functor and its argument immediately (via ap-
plication). To illustrate this intuition, consider Figure 11, which shows two deriva-
tions related to the discussion of word order in Swiss German subordinate clauses
(Shieber 1985):

. . . mer
. . . nosotros

em Hans
Hansdat

es huus
the houseacc

h¨alfed
helped

aastriche
paint

“. . . we helped Hans paint the house”

Derivation (5) (simpliﬁed from Steedman and Baldridge 2011, pag. 201) starts by com-
posing the tensed verb h¨alfed into the inﬁnitive aastriche and then applies the resulting
category to the accusative argument of the inﬁnitive, es huus. Preﬁx-closedness im-
plies that, if the combination of h¨alfed and aastriche is allowed when the latter is still
waiting for es huus, then it must also be allowed if es huus has already been found.

Cifra 11
Preﬁx-closedness predicts different word orders for Swiss German subordinate clauses.

228

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

Thus preﬁx-closedness predicts derivation (6), and along with it the alternative word
orden

. . . mer
. . . nosotros

em Hans
Hansdat

h¨alfed
helped

es huus
the houseacc

aastriche
paint

This word order is in fact grammatical (Shieber 1985, páginas. 338–339).

3.2 Generative Capacity of Preﬁx-Closed Grammars

We now show that the restriction to preﬁx-closed grammars does not change the gen-
erative capacity of VW-CCG.

Teorema 2
Preﬁx-closed VW-CCG and TAG are weakly equivalent.

Prueba
Every preﬁx-closed VW-CCG is a VW-CCG, therefore the inclusion follows from The-
orem 1. To show that every TAG language can be generated by a preﬁx-closed VW-
CCG, we recall the construction of a weakly equivalent VW-CCG for a given TAG
that we sketched in the proof of Lemma 3. As already mentioned in Example 6, el
grammar G
constructed there is not preﬁx-closed. Sin embargo, we can make it preﬁx-
closed by explicitly allowing the “missing” rule instances:

(cid:2)

Aa (cid:4) /Bc Bc (cid:2) Aa (cid:4)
Bc Aa (cid:4) /Bc (cid:2) Aa (cid:4)

dónde

A, B ∈ V
A, B ∈ V

(cid:2)

We shall now argue that this modiﬁcation does not actually change the language
generated by G
. The only categories that qualify as secondary input categories of
the new instances are atomic categories of the form Bc where B is a nonterminal of
either are of the form xa (where x is a
the TAG G. Now the lexical categories of G
terminal symbol) or are non-atomic. Categories of the form Bc are not among the derived
categories of G
either, as the combinatory rules only yield output categories whose
targets have the form Ba. This means that the new rule instances can never be used
in a complete derivation of G
, and therefore do not change the generated language.
Thus we have a construction that turns a TAG into a weakly equivalent preﬁx-closed
VW-CCG. (cid:3)

(cid:2)

3.3 Preﬁx-Closed Grammars Without Target Restrictions

In this section we shall see that the weak equivalence between preﬁx-closed VW-CCG
and TAG depends on the ability to restrict the target of the primary input category
in a combinatory rule. These are the restrictions that we referred to as constraints
of type (a) en la sección 2.2. We say that a grammar that does not make use of these
constraints is without target restrictions. This property can be formally deﬁned as
follows.

229

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Ligüística computacional

Volumen 41, Número 2

Definición 3
A VW-CCG is without target restrictions if it satisﬁes the following implication:

then so is

X/Y Yβ (cid:2) Xβ
¯X/Y Yβ (cid:2) ¯Xβ

is a valid rule instance
for any category ¯X of the grammar

and similarly for backward rules.

Ejemplo 8

Every AB-grammar is without target restrictions; it allows forward and
backward application for every primary input category.

The grammar G1 from Example (2) is not without target restrictions,
because its rules are restricted to primary input categories with target S.

Target restrictions on the primary input category are useful in CCGs for natural
idiomas; recall our discussion of backward-crossed composition in Section 1. Como nosotros
shall see, target restrictions are also relevant from a formal point of view: If we require
VW-CCGs to be without target restrictions, then we lose some of their weak generative
capacity. This is the main technical result of this article. For its proof we need the
following standard concept from formal language theory:

Definición 4
(cid:2)
Two languages L and L
permuted version w

(cid:2)

are Parikh-equivalent if for every string w ∈ L there exists a

of w such that w

, y viceversa.

(cid:2)
(cid:2) ∈ L

Teorema 3
The languages generated by preﬁx-closed VW-CCG without target restrictions are prop-
erly included in the TAG languages.

= {anbncn | n ≥ 1} from Example 5. We are interested in sublanguages L

Prueba
Every preﬁx-closed VW-CCG without target restrictions is a VW-CCG, so the inclusion
follows from Theorem 1. To see that the inclusion is proper, consider the TAG language
(cid:2) ⊆ L1 that
L1
are Parikh-equivalent to the full language L1. This property is trivially satisﬁed by L1
sí mismo. Además, it is not hard to see that L1 is in fact the only sublanguage of L1 that has
this property. Now in Section 3.4 we shall prove a central lemma (Lema 6), cual
asserts that, if we assume that L1 is generated by a preﬁx-closed VW-CCG without
target restrictions, then at least one of the Parikh-equivalent sublanguages of L1 must be
context-free. Because L1 is the only such sublanguage, this would give us proof that L1
is context-free; but we know it is not. Therefore we conclude that L1 is not generated by
a preﬁx-closed VW-CCG without target restrictions. (cid:3)

Before turning to the proof of the central lemma (Lema 6), we establish two other

results about the languages generated by grammars without target restrictions.

Lema 4
The languages generated by preﬁx-closed VW-CCG without target restrictions properly
include the context-free languages.

230

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

Prueba
Inclusion follows from the fact that AB-grammars (which generate all context-free lan-
calibres) are preﬁx-closed VW-CCGs without target restrictions. To see that the inclusion
is proper, consider a grammar G2 that is like G1 but does not have any rule restrictions.
This grammar is trivially preﬁx-closed and without target restrictions; it is actually
= L(G2)
“pure” in the sense of Kuhlmann, Koller, and Satta (2010). The language L2
= {anbncn | n ≥ 1}, together with other strings, incluido
contains all the strings in L1
the string bbbacacac, whose derivation we showed in Figure 7. It is not hard to see that
all of these additional strings have an equal number of as, bs, and cs. We can therefore
write L1 as an intersection of L2 and a regular language: L1
. To obtain a
contradiction, suppose that L2 is context-free; then because of the fact that context-free
languages are closed under intersection with regular languages, the language L1 would
be context-free as well—but we know it is not. Therefore we conclude that L2 is not
context-free either. (cid:3)

= L2

∩ a

∗
b

∗

Lema 5
The class of languages generated by preﬁx-closed VW-CCG without target restrictions
is not closed under intersection with regular languages.

Prueba
If the class of languages generated by preﬁx-closed VW-CCG without target restrictions
was closed under intersection with regular languages, then with L2 (the language
∗
mentioned in the previous proof) it would also include the language L1
.
Sin embargo, from the proof of Theorem 3 we know that L1 is not generated by any preﬁx-
closed VW-CCG without target restrictions. (cid:3)

= L2

∩ a

∗
b

∗

3.4 Proof of the Main Lemma for VW-CCG

We shall now prove the central lemma that we used in the proof of Theorem 3.

Lema 6 (Main Lemma for VW-CCG)
For every language L that is generated by some preﬁx-closed VW-CCG without target
(cid:2) ⊆ L such that
restricciones, there is a sublanguage L

(cid:2)
l
(cid:2)
l

and L are Parikh-equivalent, y

is context-free.

Throughout this section, we let G be some arbitrary preﬁx-closed VW-CCG without
target restrictions. The basic idea is to transform the derivations of G into a certain spe-
cial form, and to prove that the transformed derivations yield a context-free language.
The transformation is formalized by the rewriting system in Figure 12.4 To see how
the rules of this system work, consider rule R1; the other rules are symmetric. Rule R1
rewrites an entire derivation into another derivation. It states that, whenever we have
a situation where a category of the form X/Y is combined with a category of the form
Yβ/Z by means of composition, and the resulting category is combined with a cate-
gory Z by means of application, then we may just as well ﬁrst combine Yβ/Z with Z,
and then use the resulting category as a secondary input category together with X/Y.

4 Recall that we use the Greek letter β to denote a (possibly empty) sequence of arguments.

231

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Ligüística computacional

Volumen 41, Número 2

Cifra 12
Rewriting rules used in the transformation.

Note that R1 and R2 produce a new derivation for the original sentence, mientras
R3 and R4 produce a derivation that yields a permutation of that sentence: The order
of the substrings corresponding to the categories Z and X/Y (in the case of rule R3) o
X/Y (in the case of rule R4) is reversed. En particular, R3 captures the relation between
the two derivations of Swiss German word orders shown in Figure 11: Applying R3
to derivation (5) gives derivation (6). Importantly though, while the transformation
may reorder the yield of a derivation, every transformed derivation still is a derivation
of G.

Ejemplo 9
If we take the derivation in Figure 6 and exhaustively apply the rewriting rules from
Cifra 12, then the derivation that we obtain is the one in Figure 7. Note that although
the latter derivation is not grammatical with respect to the grammar G1 from Example 2,
it is grammatical with respect to the grammar G2 from the proof of Lemma 4, cual es
without target restrictions.

It is instructive to compare the rewriting rules in Figure 12 to the rules that establish
the normal form of Eisner (1996). This normal form is used in practical CCG parsers to
solve the problem of “spurious ambiguity,” where one and the same semantic interpre-
tation (which in CCG takes the form of a lambda term) has multiple syntactic derivation
árboles. It is established by rewriting rules such as the following:

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

X/Y Yβ/Z
Xβ/Z

†

Xβγ

Zγ

−→

X/Y

Yβ/Z Zγ
Yβγ

††

Xβγ

(5)

The rules in Figure 12 have much in common with the Eisner rules; yet there
are two important differences. Primero, as already mentioned, our rules (En particular,
rules R3 and R4) may reorder the yield of a derivation, whereas Eisner’s normal form

232

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

preserves yields. Segundo, our rules decrease the degrees of the involved composition
operaciones, whereas Eisner’s rules may in fact increase them. To see this, note that the
left-hand side of derivation (7) involves a composition of degree |b| + 1 (†), mientras
the right-hand side involves a composition of degree |b| + |γ| (††). This means that
rewriting will increase the degree in situations where |γ| > 1. A diferencia de, our rules
only ﬁre in the case where the combination with Z happens by means of an appli-
catión, eso es, si |γ| = 0. Bajo esta condición, each rewrite step is guaranteed to
decrease the degree of the composition. We will use this observation in the proof of
Lema 7.

3.4.1 Properties of the Transformation. The next two lemmas show that the rewriting
system in Figure 12 implements a total function on the derivations of G.

Lema 7
The rewriting system is terminating and conﬂuent: Rewriting a derivation ends after a
ﬁnite number of steps, and different rewriting orders all result in the same output.

Prueba
To argue that the system is terminating, we note that each rewriting step decreases
the arity of one secondary input category in the derivation by one unit, while all
other secondary input categories are left unchanged. Como ejemplo, consider rewriting
under R1. The secondary input categories in the scope of that rule are Yβ/Z and Z
on the left-hand side and Yβ and Z on the right-hand side. Here the arity of Yβ
equals the arity of Yβ/Z, minus one. Because the system is terminating, to see that it
is also conﬂuent, it sufﬁces to note that the left-hand sides of the rewrite rules do not
superposición. (cid:3)

Lema 8
The rewriting system transforms derivations of G into derivations of G.

Prueba
We prove the stronger result that every rewriting step transforms derivations of G into
derivations of G. We only consider rewriting under R1; the arguments for the other
rules are similar. Assume that R1 is applied to a derivation of G. The rule instances in
the scope of the left-hand side of R1 take the following form:

X/Y Yβ/Z (cid:2) Xβ/Z
Xβ/Z Z (cid:2) Xβ

Turning to the right-hand side, the rule instances in the rewritten derivation are

Yβ/Z Z (cid:2) Yβ
X/Y Yβ (cid:2) Xβ

(8)

(9)

(10)

(11)

The relation between instances (8) y (11) is the characteristic relation of preﬁx-
closed grammars (Definición 2): If instance (8) is valid, then because G is preﬁx-closed,

233

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Ligüística computacional

Volumen 41, Número 2

instancia (11) is valid as well. Similarmente, the relation between instances (9) y (10) es
the characteristic relation of grammars without target restrictions (Definición 3): If in-
postura (9) is valid, then because G is without target restrictions, instancia (10) is valid as
Bueno. We conclude that if R1 is applied to a derivation of G, then the result is another
derivation of G. (cid:3)

Combining Lemma 7 and Lemma 8, we see that for every derivation d of G,
exhaustive application of the rewriting rules produces another uniquely determined
derivation of G. We shall refer to this derivation as R(d). A transformed derivation is
(cid:2) = R(d) for some derivation d.
any derivation d

such that d

(cid:2)

3.4.2 Language Inclusion and Parikh-Equivalence.

Lema 9
The yields of the transformed derivations are a subset of and Parikh-equivalent to L(GRAMO).

Prueba
(cid:2) ∈ Y is obtained
Let Y be the set of yields of the transformed derivations. Every string w
from a string w ∈ L(GRAMO) by choosing some derivation d of w, rewriting this derivation
into the transformed derivation R(d), and taking the yield. Inclusion then follows from
Lema 8. Because of the permuting rules R3 and R4, the strings w and w
will in general
be different. What we can say, sin embargo, is that w and w
will be equal up to permutation.
Thus we have established that Y and L(GRAMO) are Parikh-equivalent. (cid:3)

(cid:2)

What remains in order to prove Lemma 6 is to show that the yields of the trans-

formed derivations form a context-free language.

3.4.3 Context-Freeness of the Sublanguage. In a derivation tree, every node except the root
node is labeled with either the primary or the secondary input category of a combina-
tory rule. We refer to these two types of nodes as primary nodes and secondary nodes,
respectivamente. To simplify our presentation, we shall treat the root node as a secondary
nodo. We restrict our attention to derivation trees for strings in L(GRAMO); in these trees,
the root node is labeled with the distinguished atomic category S. For a leaf node u,
the projection path of u is the path that starts at the parent of u and ends at the ﬁrst
secondary node that is encountered on the way towards the root node. We denote a
projection path as a sequence X1, . . . , Xn (n ≥ 1), where X1 is the category at the parent
of u and Xn is the category at the secondary node. Note that the category X1 is taken
from the lexicon, while every other category is derived by combining the preceding
category on the path with some secondary input category (not on the path) by means of
some combinatory rule.

Ejemplo 10
In the derivation in Figure 6, the projection path of the ﬁrst b goes all the way to
the root, while all other projection paths have length 1, starting and ending with a
lexical category. En figura 7, the projection path of the ﬁrst b ends at the root, mientras que la
projection paths of the remaining bs end at the nodes with category B, and the projection
paths of the cs end at the nodes with category C.

234

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

A projection path X1, . . . , Xn is split if it can be segmented into two parts

X1, . . . , Xs

Xs, . . . , Xn

(1 ≤ s ≤ n)

such that the ﬁrst part only uses application rules and the second part only uses
composition rules. Note that any part may consist of a single category only, en el cual
case no combinatory rule is used in that part. If n = 1, then the path is trivially split. Todo
projection paths in Figures 6 y 7 are split, except for the path of the ﬁrst b in Figure 6,
which alternates between composition (with C/A) and application (with A).

Lema 10
In transformed derivations, every projection path is split.

Prueba
We show that as long as a derivation d contains a projection path that is not split, él
can be rewritten. A projection path that is not split contains three adjacent categories
Ud., V, W., such that V is derived by means of a composition with primary input U, and W
is derived by means of an application with primary input V. Suppose that both the
composition and the application are forward. (The arguments for the other three cases
are similar.) Then U can be written as X/Y for some category X and argument /Y, V
can be written as Xβ/Z for some argument /Z and some (possibly empty) secuencia
of arguments β, and W can be written as Xβ. We can then convince ourselves that d
contains the following conﬁguration, which matches the left-hand side of rewriting
rule R1:

X/Y Yβ/Z
Xβ/Z

Xβ

(cid:3)

Lema 11
The set of all categories that occur in transformed derivations is ﬁnite.

Prueba
Every category that occurs in transformed derivations occurs on some of its projection
paths. Consider any such path. Por Lema 10 we know that this path is split; its two
partes, here called P1 and P2, are visualized in Figure 13. We now reason about the arities
of the categories in these two parts.

Because P1 only uses application, the arities in this part get smaller and
smaller until they reach their minimum at Xs. This means that the arities
of P1 are bounded by the arity of the ﬁrst category on the path, which is a
category from the lexicon.

Because P2 only uses composition, the arities in this part either get larger
or stay the same until they reach a maximum at Xn. This means that the
arities of P2 are bounded by the arity of the last category on the path,
which is either the distinguished atomic category S or a secondary input
categoría.

235

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Ligüística computacional

Volumen 41, Número 2

Cifra 13
Illustration of the argument used in the proof of Lemma 11.

Thus the arities of our chosen path are bounded by the maximum of three grammar-
speciﬁc constants: the maximal arity of a lexical category, the arity of S (cual es 0),
and the maximal arity of a secondary input category. The latter value is well-deﬁned
because there are only ﬁnitely many such categories (by Lemma 2). Let k be the
maximum among the three constants, and let K be the set of all categories of the
form A|
iXi is an
argument that may occur in derivations of G. The set K contains all categories that
occur on some projection path, and therefore all categories that occur in transformed
derivations, but it may also include other categories. As there are only ﬁnitely many
atomic categories and ﬁnitely many arguments (Lema 1), we conclude that the set K,
and hence the set of categories that occur in transformed derivations, are ﬁnite as
Bueno. (cid:3)

1X1 where A is an atomic category of G, m ≤ k, and each |

mXm

· · · |

Lema 12
The transformed derivations yield a context-free language.

Prueba
We construct a context-free grammar H that generates the set Y of yields of the trans-
formed derivations. To simplify the presentation, we ﬁrst construct a grammar H
eso
generates a superset of Y.

(cid:2)

. The construction of the grammar H

Construction of H
is the same as the construction
in the classical proof that showed the context-freeness of AB-grammars, by Bar-Hillel,
Gaifman, and Shamir (1960): The production rules of H
are set up to correspond to the
valid rule instances of G. The reason that this construction is not useful for VW-CCGs
in general is that these may admit inﬁnitely many rule instances, whereas a context-free
grammar can only have ﬁnitely many productions. The set of rule instances may be
inﬁnite because VW-CCG has access to composition rules (speciﬁcally, rules of degrees
greater than 1); in contrast, AB-grammars are restricted to application. Crucially though,
by Lemma 11 we know that as long as we are interested only in transformed derivations
it is sufﬁcient to use a ﬁnite number of rule instances—more speciﬁcally those whose
input and output categories are included in the set K of arity-bounded categories. De este modo
for every instance X/Y Yβ (cid:2) Xβ where all three categories are in K, construimos un
producción

[Xβ] → [X/Y] [Yβ]

236

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

and similarly for backward rules. (We enclose categories in square brackets for clarity.)
Además, for every lexicon entry σ := X in G we add to H
a production [X] → σ.
(cid:2)
As the terminal alphabet of H
we choose the vocabulary of G; as the nonterminal
alphabet we choose the set K; and as the start symbol we choose the distinguished
atomic category S. Every transformed derivation of G corresponds (in an obvious way)
to some derivation in H
). En cambio, every derivation
represents a derivation of G (though not necessarily a transformed derivation),
of H
thus L(h

, which proves that Y ⊆ L(h

) ⊆ L(GRAMO).

(cid:2)

) y yo(GRAMO), which means that L(h

Construction of H. The chain of inclusions Y ⊆ L(h
) ⊆ L(GRAMO) is sufﬁcient to prove
Lema 6: Because Y and L(GRAMO) are Parikh-equivalent (which we observed at the be-
ginning of Section 3.4.2), so are L(h
) satisﬁes all
of the properties claimed in Lemma 6, even though this does not sufﬁce to prove our
is given, it is not hard to also obtain a grammar H that
current lemma. Sin embargo, once H
generates exactly Y. Para esto, we need to ﬁlter out derivations whose projection paths do
not have the characteristic property of transformed derivations that we established in
Lema 10. (It is not hard to see that every derivation that does have this property is
a transformed derivation.) We annotate the left-hand side nonterminals in the produc-
with a ﬂag t ∈ {a, C} to reﬂect whether the corresponding category has been
tions of H
derived by means of application (t = a) or composition (t = c); the value of this ﬂag is
simply the type of combinatory rule that gave rise to the production. The nonterminals
in the right-hand sides are annotated in all possible ways, except that the following
combinations are ruled out:

(cid:2)

[X]a

→ [X/Y]C[Y]t

y [X]a

→ [Y]t[X/Y]C

t ∈ {a, C}

These combinations represent exactly the cases where the output category of a compo-
sition rule is used as the primary input category of an application rule, which are the
cases that violate the “split” property that we established in Lemma 10. (cid:3)

This concludes the proof of Lemma 6, and therefore the proof of Theorem 3.

3.5 Discusión

Teorema 3 pinpoints the exact mechanism that VW-CCG uses to achieve weak equiv-
alence to TAG: At least for the class of preﬁx-closed grammars, TAG equivalence is
achieved if and only if we allow target restrictions. Although target restrictions are
frequently used in linguistically motivated grammars, it is important and perhaps
surprising to realize that they are indeed necessary to achieve the full generative capacity
of VW-CCG.

In the grammar formalisms folklore, the generative capacity of CCG is often at-
tributed to generalized composition, and indeed we have seen (in Lemma 4) that even
grammars without target restrictions can generate non-context-free languages such as
l(G2). Sin embargo, our results show that composition by itself is not enough to achieve
weak equivalence with TAG: The yields of the transformed derivations from Section 3.4
form a context-free language despite the fact that these derivations may still contain
compositions, including compositions of degree n > 2. In addition to composition, VW-
CCG also needs target restrictions to exert enough control on word order to block
unwanted permutations. One way to think about this is that target restrictions can
enforce alternations of composition and application (as in the derivation shown in

237

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Ligüística computacional

Volumen 41, Número 2

Cifra 6), while transformed derivations are characterized by projection paths without
such alternations (Lema 10).

We can sharpen the picture even more by observing that the target restrictions
that are crucial for the generative capacity of VW-CCG are not those on generalized
composition, but those on function application. To see this we can note that the proof
of Lemma 8 goes through also only if application rules such as (9) y (10) are without
target restrictions. This means that we have the following qualiﬁcation of Theorem 1.

Lema 13
Preﬁx-closed VW-CCG is weakly equivalent to TAG only because it supports target
restrictions on forward and backward application.

This ﬁnding is unexpected indeed—for instance, no grammar in Steedman (2000)

uses target restrictions on the application rules.

4. Generative Capacity of Multimodal CCG

After clarifying the mechanisms that “classical” CCG uses to achieve weak equivalence
with TAG, we now turn our attention to “modern,” multimodal versions of CCG
(Baldridge and Kruijff 2003; Steedman and Baldridge 2011). These versions emphasize
the use of fully lexicalized grammars in which no rule restrictions are allowed, y
instead equip slashes with types in order to control the use of the combinatory rules.
Our central question is whether the use of slash types is sufﬁcient to recover the
expressiveness that we lose by giving up rule restrictions.

We need to ﬁx a speciﬁc variant of multimodal CCG to study this question formally.
Published works on multimodal CCG differ with respect to the speciﬁc inventories of
slash types they assume. Some important details, such as a precise deﬁnition of gener-
alized composition with slash types, are typically not discussed at all. In this article we
deﬁne a variant of multimodal CCG which we call O-CCG. This formalism extends our
deﬁnition of VW-CCG (Definición 1) with the slash inventory and the composition rules
of the popular OpenCCG grammar development system (Blanco 2013). Our technical
result is that the main Lemma (Lema 6) also holds for O-CCG. With this we can
conclude that the answer to our question is negative: Slash types are not sufﬁcient to
replace rule restrictions; O-CCG is strictly less powerful than TAG. Although this is
primarily a theoretical result, at the end of this section we also discuss its implications
for practical grammar development.

4.1 Multimodal CCG

We deﬁne O-CCG as a formalism that extends VW-CCG with the slash types of
OpenCCG, but abandons rule restrictions. Note that OpenCCG has a number of ad-
ditional features that affect the generative capacity; we discuss these in Section 4.4.

Slash Types. Like other incarnations of multimodal CCG, O-CCG uses an enriched notion
of categories where every slash has a type. There are eight such types:5

core types:

∗

(cid:11) × ·

left types: (cid:5) (cid:5)×

right types: (cid:6) ×(cid:6)

5 The type system of OpenCCG is an extension of the system used by Baldridge (2002).

238

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

Cifra 14
Compatibility of slash types with combinatory rules.

The basic idea behind these types is as follows. Slashes with type ∗ can only be used
to instantiate application rules. Tipo (cid:11) also licenses harmonic composition rules, y
type × also licenses crossed composition rules. Type · is the least restrictive type and
can be used to instantiate all rules. The remaining types reﬁne the system by incorpo-
rating a dimension of directionality. The exact type–rule compatibilities are speciﬁed in
Cifra 14.

Inertness. O-CCG is distinguished from other versions of multimodal CCG, como eso
of Baldridge and Kruijff (2003), in that every slash not only has a type but also an
inertness status. Inertness was introduced by Baldridge (2002, Sección 8.2.2) as an im-
plementation of the “antecedent government” (ANT) feature of Steedman (1996), cual
is used to control the word order in certain English relative clauses. It is a two-valued
feature. Arguments whose slash type has inertness status + are called active; argumentos
whose slash type has inertness status − are called inert. Only active arguments can
be eliminated by means of combinatory rules; sin embargo, an inert argument can still be
consumed as part of a secondary input category. Por ejemplo, the following instance
of application is valid because the outermost slash of the primary input category has
inertness status +:

X/+

(Y/−

z) Y/−

z (cid:2) X

We use the notations /s
t and /s
slash type t and inertness status s.

t to denote the forward and backward slashes with

Rules. All O-CCG grammars share a ﬁxed set of combinatory rules, como se muestra en la figura 15.
Every grammar uses all rules, up to some grammar-speciﬁc bound on the degree of
generalized composition. As mentioned earlier, a combinatory rule can only be in-
stantiated if the slashes of the input categories have compatible types. Además,
all composition rules require the slashes of the secondary input category to have a
uniform direction. This is a somewhat peculiar feature of OpenCCG, and is in contrast
to VW-CCG and other versions of CCG, which also allow composition rules with mixed
directions.

Composition rules are classiﬁed into harmonic and crossed forms. This distinction
is based on the direction of the slashes in the secondary input category. If these have
the same direction as the outermost slash of the primary input category, then the rule is
called harmonic; otherwise it is called crossed.6

6 In versions of CCG that allow rules with mixed slash directions, the distinction between harmonic and

crossed is made based on the direction of the innermost slash of the secondary input category, |

239

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Ligüística computacional

Volumen 41, Número 2

Cifra 15
The rules of O-CCG. For a rule to apply, all slashes in the scope of the rule must have one of the
speciﬁed compatible types (cf. Cifra 14). The predicates left(t)/bien(t) are true if and only if t is
equal to either a left/right type or one of the four undirected core types.

When a rule is applied, in most cases the arguments of the secondary input category
are simply copied into the output category, as in VW-CCG. The one exception happens
for crossed composition rules if not all slash directions match the direction of their
slash type (left or right). En este caso, the arguments of the secondary input category
become inert. Thus the inertness status of an argument may change over the course of
a derivation—but only from active to inert, not back again.

Definición 5
A multimodal combinatory categorial grammar in the sense of OpenCCG, or O-CCG
for short, is a structure

G = (S, A, :=, d, S)

where Σ is a ﬁnite vocabulary, A is a ﬁnite set of atomic categories, := is a ﬁnite relation
between Σ and the set of (multimodal) categories over A, d ≥ 0 is the maximal degree
of generalized composition, and S ∈ A is a distinguished atomic category.

We generalize the notions of rule instances, derivation trees, and generated lan-
guage to categories over slashes with types and inertness statuses in the obvious way:
Instead of two slashes, we now have one slash for every combination of a direction,
tipo, and inertness status. Similarmente, we generalize the concepts of a grammar being
preﬁx-closed (Definición 2) and without target restrictions (Definición 3) to O-CCG.

240

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

4.2 Generative Capacity

We now investigate the generative capacity of O-CCG. We start with the (unsurprising)
observation that O-CCG can describe non-context-free languages.

Lema 14
The languages generated by O-CCG properly include the context-free languages.

Prueba
Inclusion follows from the fact that every AB-grammar can be written as an O-CCG
with only application (re = 0). To show that the inclusion is proper, we use the same
argument as in the proof of Lemma 4. The grammar G2 that we constructed there can
be turned into an equivalent O-CCG by decorating each slash with ·, the least restrictive
tipo, and setting its inertness status to +. (cid:3)

What is less obvious is whether O-CCG generates the same class of languages as

VW-CCG and TAG. Our main result is that this is not the case.

Teorema 4
The languages generated by O-CCG are properly included in the TAG languages.

O-CCG without Inertness. To approach Theorem 4, we set inertness aside for a moment
and focus on the use of the slash types as a mechanism for imposing rule restrictions.
Each of the rules in Figure 15 requires all of the slash types of the n outermost arguments
of its secondary input category to be compatible with the rule, in the sense speciﬁed
En figura 14. If we now remove one or more of these arguments from a valid rule
instancia, then the new instance is clearly still valid, as we have reduced the number
of potential violations of the type–rule compatibility. This shows that the rule system
is preﬁx-closed. As none of the rules is conditioned on the target of the primary input
categoría, the rule system is even without target restrictions. With these two properties
established, Teorema 4 can be proved by literally the same arguments as those that we
gave in Section 3. Thus we see directly that the theorem holds for versions of multi-
modal CCG without inertness, such as the formalism of Baldridge and Kruijff (2003).

O-CCG with Inertness. In the general case, the situation is complicated by the fact that
the crossed composition rules change the inertness status of some argument categories
if the slash types have conﬂicting directions. This means that the crossed composition
rules in O-CCG are not entirely preﬁx-closed, as illustrated by the following example.

Ejemplo 11
Consider the following two rule instances:

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

X/+

×(cid:2)Y Y/+
X/+

(cid:3)×Z2
×(cid:2)Y Y/+

/+
×(cid:2)Z1

(cid:3)×Z2

(cid:2) X/−
(cid:2) X/−

(cid:3)×Z2

/−
×(cid:2)Z1

(12)

(13)

Instance (12) is a valid instance of forward crossed composition. Preﬁx-closedness
would require instance (13) to be valid as well; but it is not. In instance (12) the inertness
status of /+
(cid:3)×Z2 is changed for the only reason that the slash type of /+
×(cid:2)Z1 does not
match the required direction. In instance (13) the argument /+
×(cid:2)Z1 is not present, y

241

Ligüística computacional

Volumen 41, Número 2

therefore the inertness status of /+
categoría.

(cid:3)×Z2 is not changed, but is carried over to the output

We therefore have to prove that the following analogue of Lemma 6 holds for

O-CCG:

Lema 15 (Main Lemma for O-CCG)
For every language L generated by some O-CCG there is a sublanguage L

(cid:2) ⊆ L such that

(cid:2)
l
(cid:2)
l

and L are Parikh-equivalent, y

is context-free.

= {anbncn | n ≥ 1} from Example 2 cannot be
This lemma implies that the language L1
generated by O-CCG (but by preﬁx-closed VW-CCG with target restrictions, and by
TAG). The argument is the same as in the proof of Theorem 3.

4.3 Proof of the Main Lemma for O-CCG

The proof of Lemma 15 adapts the rewriting system from Figure 12. We simply let
each rewriting step copy the type and inertness status of each slash from the left-hand
side to the right-hand side of the rewriting rule. With this change, it is easy to verify
that the proofs of Lemma 7 (termination and conﬂuence), Lema 10 (projection paths
in transformed derivations are split), Lema 11 (transformed derivations contain a
ﬁnite number of categories), and Lemma 12 (transformed derivations yield a context-
free language) go through without problems. The proof of Lemma 8, sin embargo, is not
straightforward, because of the dynamic nature of the inertness statuses. We therefore
restate the lemma for O-CCG:

Lema 16
The rewriting system transforms O-CCG derivations into O-CCG derivations.

Prueba
As in the proof of Lemma 8 we establish the stronger result that the claimed property
holds for every single rewriting step. We only give the argument for rewriting under R3,
which involves instances of forward crossed composition. The argument for R4 is anal-
ogous, and R1 and R2 are simpler cases because they involve harmonic composition,
where the inertness status does not change.

Suppose that R3 is applied to a derivation of some O-CCG. In their most general
forma, the rule instances in the scope of the left-hand side of R3 may be written as follows,
where the function σ is deﬁned as speciﬁed in Figure 15:

X/+
t0

Y Y/sn
tn

· · · /s2
t2

/s1
t1

(cid:2) X/σ(sn)

· · · /σ(s2 )
t2

/pag(s1 )
t1

Z1 X/σ(sn)

· · · /σ(s2 )
t2

/+
t1

(cid:2) X/σ(sn)

· · · /σ(s2 )
t1

(14)

(15)

242

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

Here instance (14) is an instance of forward-crossed composition, so each of the types ti
is compatible with that rule. Because the two marked arguments are identical, tenemos
pag(s1) = +. This is only possible if the inertness statuses of the slashes /si
do not change
de
in the context of derivation (14), eso es, if σ(si) = si for all 1 ≤ yo ≤ norte. Tenga en cuenta que en
este caso, t0 is either a right type or one of the four undirected core types, and each
t1, . . . , tn is either a left type or a core type. We can now alternatively write instances (14)
y (15) como

X/+
Y Y/sn
t0
tn
Z1 X/sn
tn

· · · /s2
t2
· · · /s2
t2

/+
t1
/+
t1

(cid:2) X/sn
tn
(cid:2) X/sn
tn

· · · /s2
t2
· · · /s2
t1

/+
t1

Then the rule instances in the rewritten derivation can be written as follows:

Z1 Y/sn
Zn
tn
X/+
Y Y/sn
tn
t0

/+
· · · /s2
t1
t2
· · · /s2
t2

(cid:2) Y/sn
tn
(cid:2) X/sn
tn

· · · /s2
t2
· · · /s2
t2

(14

(15

(cid:2)

)

(16)

(17)

Here instance (16) is clearly a valid instance of backward application. Based on our
earlier observations about the ti and their compatibility with crossed composition, nosotros
also see that instance (17) is a valid instance of forward crossed composition (if n > 1),
or of forward application (if n = 1). (cid:3)

This completes the proof of Lemma 15. To ﬁnish the proof of Theorem 4 tenemos
to also establish the inclusion of the O-CCG languages in the TAG languages. Esto es
a known result for other dialects of multimodal CCG (Baldridge and Kruijff 2003), pero
O-CCG once again requires some extra work because of inertness.

Lema 17
The O-CCG languages are included in the TAG languages.

Prueba (Sketch)
It sufﬁces to show that the O-CCG languages are included in the class of languages
generated by LIG (Gazdar 1987); the claim then follows from the weak equivalence of
LIG and TAG. Vijay-Shanker and Weir (1994, Sección 3.1) present a construction that
transforms an arbitrary VW-CCG into a weakly equivalent LIG. It is straightforward to
adapt their construction to O-CCG. As we do not have the space here to deﬁne LIG, nosotros
only provide a sketch of the adapted construction.

As in the case of VW-CCG, the valid instances of an O-CCG rule can be writ-
ten down using our template notation. The adapted construction converts each such
template into a production rule of a weakly equivalent LIG. Consider for instance the
following instance of forward crossed composition from Example 11:

A (cid:4) /+

×(cid:2)Y Y/+

(cid:3)×Z2

/+
×(cid:2)Z1

(cid:2) A (cid:4) /−

(cid:3)×Z2

/−
×(cid:2)Z1

243

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Ligüística computacional

Volumen 41, Número 2

This template is converted into the following LIG rule. We adopt the notation of Vijay-
Shanker and Weir (1994) and write ◦◦ for the tail of a stack of unbounded size.

A[◦◦/−

(cid:3)×Z2

/−
×(cid:2)Z1] → A[◦◦/+

×(cid:2)Y] Y[/+

(cid:3)×Z2

/+
×(cid:2)Z1]

In this way, every O-CCG can be written as a weakly equivalent LIG. (cid:3)

4.4 Discusión

In this section we have shown that the languages generated by O-CCG are properly
included in the languages generated by TAG, and equivalently, in the languages gen-
erated by VW-CCG. This means that the multimodal machinery of OpenCCG is not
powerful enough to express the rule restrictions of VW-CCG in a fully lexicalized
way. The result is easy to obtain for O-CCG without inertness, which is preﬁx-closed
and without target restrictions; but it is remarkably robust in that it also applies to
O-CCG with inertness, which is not preﬁx-closed. As we have already mentioned, el
result carries over also to other multimodal versions of CCG, such as the formalism of
Baldridge and Kruijff (2003).

Our result has implications for practical grammar development with OpenCCG.
Para ilustrar esto, recall Example 7, which showed that every VW-CCG without target
restrictions for Swiss German that allows cross–serial word orders as in derivation (5)
also permits alternative word orders, as in derivation (6). Por Lema 15, this remains
true for O-CCG or weaker multimodal formalisms. This is not a problem in the case
of Swiss German, where the alternative word orders are grammatical. Sin embargo, allá
is at least one language, Dutch, where dependencies in subordinate clauses must cross.
For this case, our result shows that the modalized composition rules of OpenCCG are
not powerful enough to write adequate grammars. Consider the following classical
ejemplo:

. . .
. . .

ik Cecilia
Cecilia
I

de paarden
the horses

voeren

zag
saw feed

“. . . I saw Cecilia feed the horses”

The straightforward derivation of the cross–serial dependencies in this sentence
(adapted from Steedman 2000, pag. 141) is exempliﬁed in Figure 16. It takes the same
form as derivation (5) for Swiss German: The verbs and their NP arguments lie on a
single, right-branching path projected from the tensed verb zag. This projection path is
not split; speciﬁcally, it starts with a composition that produces a category which acts
as the primary input category of an application. Como consecuencia, the derivation can
be transformed (by our rewriting rule R3) in exactly the same way as instance (5) podría
be transformed into derivation (6). The crucial difference is that the yield of the trans-
formed derivation, *ik Cecilia zag de paarden voeren, is not a grammatical clause of Dutch.
To address the problem of ungrammatical word orders in Dutch subordinate
clausulas, the VW-CCG grammar of Steedman (2000) and the multimodal CCG grammar
of Baldridge (2002, Sección 5.3.1) resort to combinatorial rules other than composi-
ción. En particular, they assume that all complement noun phrases undergo obligatory
type-raising, and become primary input categories of application rules. This gives
rise to derivations such as the one shown in Figure 17, which cannot be transformed
using our rewriting rules because the result of the forward crossed composition >1

244

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

Cifra 16
Straightforward derivation of Dutch cross–serial dependencies.

Cifra 17
Derivation of Dutch cross–serial dependencies with type-raised noun complements.

now is a secondary rather than a primary input category. Como consecuencia, este
grammar is capable of enforcing the obligatory cross-serial dependencies of Dutch.
Sin embargo, it is important to note that it requires type-raising over arbitary categories
with target S (observe the increasingly complex type-raised categories for the NPs).
This kind of type-raising is allowed in many variants of CCG, including the full for-
malism underlying OpenCCG. VW-CCG and O-CCG, sin embargo, are limited to gen-
eralized composition, and can only support derivations like the one in Figure 17 si
all the type-raised categories for the noun phrases are available in the lexicon. El
unbounded type-raising required by the Steedman–Baldridge analysis of Dutch would
translate into an inﬁnite lexicon, and so this analysis is not possible in VW-CCG and
O-CCG.

We conclude by discussing the impact of several other constructs of OpenCCG
that we have not captured in O-CCG. Primero, OpenCCG allows us to use generalized
composition rules of arbitrary degree; there is no upper bound d on the composi-
tion degree as in an O-CCG grammar. It is known that this extends the generative
capacity of CCG beyond that of TAG (Weir 1988). Segundo, OpenCCG allows cate-
gories to be annotated with feature structures. This has no impact on the generative
capacity, as the features must take values from ﬁnite domains and can therefore be
compiled into the atomic categories of the grammar. Finalmente, OpenCCG includes the
combinatory rules of substitution and coordination, as well as multiset slashes, un-
other extension frequently used in linguistic grammars. We have deliberately left these
constructs out of O-CCG to establish the most direct comparison to the literature on
VW-CCG. It is conceivable that their inclusion could restore the weak equivalence
to TAG, but a proof of this result would require a non-trivial extension of the work
of Vijay-Shanker and Weir (1994). Regarding multiset slashes, it is also worth noting
that these were introduced with the expressed goal of allowing more ﬂexible word

245

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Ligüística computacional

Volumen 41, Número 2

orden, whereas restoration of weak equivalence would require more controlled word
orden.

5. Conclusión

In this article we have contributed two technical results to the literature on CCG. Primero,
we have reﬁned the weak equivalence result for CCG and TAG (Vijay-Shanker and
Weir 1994) by showing that preﬁx-closed grammars are weakly equivalent to TAG
only if target restrictions are allowed. Segundo, we have shown that O-CCG, the formal,
composition-only core of OpenCCG, is not weakly equivalent to TAG. Estos resultados
point to a tension in CCG between lexicalization and generative capacity: Lexicalized
versions of the framework are less powerful than classical versions, which allow rule
restricciones.

What conclusions one draws from these technical results depends on the perspec-
tivo. One way to look at CCG is as a system for deﬁning formal languages. Under this
vista, one is primarily interested in results on generative capacity and parsing complex-
ity such as those obtained by Vijay-Shanker and Weir (1993, 1994). Aquí, nuestros resultados
clarify the precise mechanisms that make CCG weakly equivalent to TAG. Tal vez
surprisingly, it is not the availability of generalized composition rules by itself that ex-
plains the generative power of CCG, but the ability to constrain the interaction between
generalized composition and function application by means of target restrictions.

Por otro lado, one may be interested in CCG primarily as a formalism for
developing grammars for natural languages (Steedman 2000; Baldridge 2002; Steedman
2012). From this point of view, the suitability of CCG for the development of lexicalized
grammars has been amply demonstrated. Sin embargo, our technical results still serve
as important reminders that extra care must be taken to avoid overgeneration when
designing a grammar. En particular, it is worth double-checking that an OpenCCG
grammar does not generate word orders that the grammar developer did not intend.
Here the rewriting system that we presented in Figure 12 can serve as a useful tool:
A grammar developer can take any derivation for a grammatical sentence, transform
the derivation according to our rewriting rules, and check whether the transformed
derivation still yields a grammatical sentence.

It remains an open question how the conﬂicting desires for generative capacity
and lexicalization might be reconciled. A simple answer is to add some lexicalized
method for enforcing target restrictions to CCG, speciﬁcally on the application rules.
Sin embargo, we are not aware that this idea has seen widespread use in the CCG literature,
so it may not be called for empirically. Alternativamente, one might modify the rules of
O-CCG in such a way that they are no longer preﬁx-closed—for example, by introducing
some new slash type. Finalmente, it is possible that the constructs of OpenCCG that we
set aside in O-CCG (such as type-raising, substitution, and multiset slashes) might be
sufﬁcient to achieve the generative capacity of classical CCG and TAG. A detailed study
of the expressive power of these constructs would make an interesting avenue for future
investigación.

Expresiones de gratitud
We are grateful to Mark Steedman and Jason
Baldridge for enlightening discussions of the
material presented in this article, and to the
four anonymous reviewers of the article for
their detailed and constructive comments.

Referencias
Ajdukiewicz, Kazimierz. 1935. Die
syntaktische Konnexit¨at. Studia
Philosophica, 1:1–27.

Baldridge, Jason. 2002. Lexically Speciﬁed
Derivational Control in Combinatory

246

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
/

a
r
t
i
C
mi
–
pag
d

F
/

4
1
2
2
1
5
1
8
0
4
9
4
7
/
C
oh

yo
i

_
a
_
0
0
2
1
9
pag
d

b
y
gramo
tu
mi
s
t

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

Kuhlmann, Koller, and Satta

Lexicalization and Generative Power in CCG

Categorial Grammar. Doctor. tesis,
University of Edinburgh, Edimburgo, Reino Unido.

Baldridge, Jason and Geert-Jan M. Kruijff.

2003. Multi-modal combinatory categorial
gramática. In Tenth Conference of the
European Chapter of the Association for
Ligüística computacional (EACL),
pages 211–218, Budapest.

Bar-Hillel, Yehoshua, Haim Gaifman, and Eli
Shamir. 1960. On categorial and phrase
structure grammars. Bulletin of the Research
Council of Israel, 9F(1):1-dieciséis. Reprinted in
Yehoshua Bar-Hillel. Language and
Información: Selected Essays on Their Theory
and Application, pages 99–115.
Addison-Wesley, 1964.

Curry, Haskell B., Robert Feys, and William
Craig. 1958. Combinatory Logic. Volumen 1.
Studies in Logic and the Foundations of
Matemáticas. Holanda Septentrional.

Eisner, Jason. 1996. Efﬁcient normal-form
parsing for Combinatory Categorial
Grammar. In Proceedings of the 34th Annual
Meeting of the Association for Computational
Lingüística (LCA), pages 79–86,
Santa Cruz, California.

Gazdar, Gerald. 1987. Applicability of

indexed grammars to natural language. En
Uwe Reyle and Christian Rohrer, editores,
Natural Language Parsing and Linguistic
Theories. D. Reidel, pages 69–94.
Joshi, Aravind K. 1985. Tree Adjoining

Grammars: How much context-sensitivity
is required to provide reasonable
structural descriptions? In David R.
Dowty, Lauri Karttunen, and Arnold M.
Zwicky, editores, Natural Language Parsing.
Prensa de la Universidad de Cambridge,
pages 206–250.

Joshi, Aravind K. and Yves Schabes. 1997.
Tree-Adjoining Grammars. In Grzegorz
Rozenberg and Arto Salomaa, editores,
Handbook of Formal Languages, volumen 3.
Saltador, pages 69–123.

Kuhlmann, Marco, Alejandro Koller, y

Giorgio Satta. 2010. The importance of rule
restrictions in CCG. En Actas de la
48ª Reunión Anual de la Asociación de
Ligüística computacional (LCA),
pages 534–543, Uppsala.

Moortgat, Miguel. 2011. Categorial type

logics. In Johan van Benthem and Alice ter

Meulen, editores, Handbook of Logic and
Idioma. Elsevier, second edition,
capítulo 2, pages 95–179.

Pollard, Carl J. 1984. Generalized Phrase

Structure Grammars, Head Grammars, y
Natural Language. Doctor. tesis, stanford
Universidad.

Shieber, Stuart M. 1985. Evidence against the

context-freeness of natural language.
Lingüística y Filosofía, 8(3):333–343.
Steedman, Marca. 1996. Surface Structure and
Interpretation, volumen 30 of Linguistic
Inquiry Monographs. CON prensa.

Steedman, Marca. 2000. The Syntactic Process.

CON prensa.

Steedman, Marca. 2012. Taking Scope. CON

Prensa.

Steedman, Mark and Jason Baldridge. 2011.
Combinatory Categorial Grammar. En
Roberto D.. Borsley and Kersti B ¨orjars,
editores, Non-Transformational Syntax:
Formal and Explicit Models of Grammar.
Blackwell, capítulo 5, pages 181–224.
Vijay-Shanker, k. y David J.. Weir. 1993.
Parsing some constrained grammar
formalisms. Ligüística computacional,
19(4):591–636.

Vijay-Shanker, k. y David J.. Weir. 1994.
The equivalence of four extensions of
context-free grammars. Matemático
Systems Theory, 27(6):511–546.

Vijay-Shanker, K., David J. Weir, y

Aravind K. Joshi. 1986. Tree adjoining and
head wrapping. En Actas de la
Eleventh International Conference on
Ligüística computacional (COLECCIONAR),
pages 202–207, Bonn.

Weir, David J. 1988. Characterizing Mildly
Context-Sensitive Grammar Formalisms.
Doctor. tesis, Universidad de Pennsylvania.

Weir, David J. and Aravind K. Joshi. 1988.
Combinatory categorial grammars:
Generative power and relationship to
linear context-free rewriting systems.
In Proceedings of the 26th Annual Meeting
of the Association for Computational
Lingüística (LCA), pages 278–285,
Buffalo, Nueva York.