Skip to main navigation menu Skip to main content Skip to site footer

Vol. 2 (2014)

TACL approved

A New Parsing Algorithm for Combinatory Categorial Grammar

Published 2014-10-07

  • Marco Kuhlmann
    • ,
  • Giorgio Satta

Marco Kuhlmann
Linköping University

Giorgio Satta
University of Padova

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.
PDF