  We study the parsing complexity of Combinatory Categorial Grammar (CCG) in
the formalism of Vijay-Shanker and Weir (1994). As our main result, we prove
that any parsing algorithm for this formalism will take in the worst case
exponential time when the size of the grammar, and not only the length of the
input sentence, is included in the analysis. This sets the formalism of
Vijay-Shanker and Weir (1994) apart from weakly equivalent formalisms such as
Tree-Adjoining Grammar (TAG), for which parsing can be performed in time
polynomial in the combined size of grammar and input sentence. Our results
contribute to a refined understanding of the class of mildly context-sensitive
grammars, and inform the search for new, mildly context-sensitive versions of
CCG.
