Hide menu

A New Parsing Algorithm for Combinatory Categorial Grammar

Marco Kuhlmann and Giorgio Satta. A New Parsing Algorithm for Combinatory Categorial Grammar. Transactions of the Association for Computational Linguistics, 2(Oct):405–418, 2014.

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(n^6)$, as a previous algorithm by Vijay-Shanker and Weir (1993), but is easier to understand, implement, and prove correct.

Links


Page responsible: Marco Kuhlmann
Last updated: 2017-09-25