On the Complexity of CCG Parsing
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Discriminative Syntax-Based Word Ordering for Text GenerationComputational Linguistics, 2015
- Lexicalization and Generative Power in CCGComputational Linguistics, 2015
- A New Parsing Algorithm for Combinatory Categorial GrammarTransactions of the Association for Computational Linguistics, 2014
- Complexity of Equations over Sets of Natural NumbersTheory of Computing Systems, 2009
- Wide-Coverage Efficient Statistical Parsing with CCG and Log-Linear ModelsComputational Linguistics, 2007
- CCGbank: A Corpus of CCG Derivations and Dependency Structures Extracted from the Penn TreebankComputational Linguistics, 2007
- On multiple context-free grammarsTheoretical Computer Science, 1991
- On the Succinctness of Different Representations of LanguagesSIAM Journal on Computing, 1980