A New Parsing Algorithm for Combinatory Categorial Grammar

Marco Kuhlmann, Giorgio Satta


We present a polynomial-time parsing algorithm for CCG, based on a new decomposition of derivations into small, shareable parts.Our algorithm has the same asymptotic complexity, $O(n^6)$, as a previous algorithm by Vijay-Shanker and Weir (1993), but is easier to understand, implement, and prove correct.

Full Text:



  • There are currently no refbacks.

Copyright (c) 2014 Association for Computational Linguistics

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.