Peter Jönsson

On the Complexity of CCG Parsing

2017 · arXiv (Cornell University)

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 …