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:
Venue:
TACL
SIG:
Publisher:
Note:
Pages:
405–418
Language:
URL:
https://www.aclweb.org/anthology/Q14-1032
DOI:
10.1162/tacl_a_00192
Bib Export formats:
BibTeX MODS XML EndNote
PDF:
http://aclanthology.lst.uni-saarland.de/Q14-1032.pdf