A New Parsing Algorithm for Combinatory Categorial Grammar

Marco Kuhlmann, Giorgio Satta


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
Bibkey:
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)
Copy Citation:
PDF:
https://aclanthology.org/Q14-1032.pdf