Abstract
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(n6), as a previous algorithm by Vijay-Shanker and Weir (1993), but is easier to understand, implement, and prove correct.- Anthology ID:
- Q14-1032
- Volume:
- Transactions of the Association for Computational Linguistics, Volume 2
- Month:
- Year:
- 2014
- Address:
- Cambridge, MA
- Editors:
- Dekang Lin, Michael Collins, Lillian Lee
- Venue:
- TACL
- SIG:
- Publisher:
- MIT Press
- Note:
- Pages:
- 405–418
- Language:
- URL:
- https://aclanthology.org/Q14-1032
- DOI:
- 10.1162/tacl_a_00192
- Cite (ACL):
- Marco Kuhlmann and Giorgio Satta. 2014. A New Parsing Algorithm for Combinatory Categorial Grammar. Transactions of the Association for Computational Linguistics, 2:405–418.
- Cite (Informal):
- A New Parsing Algorithm for Combinatory Categorial Grammar (Kuhlmann & Satta, TACL 2014)
- PDF:
- https://preview.aclanthology.org/fix-dup-bibkey/Q14-1032.pdf