The complexity of parsing with extended categorial grammars
Esther König · 1990
Instead of incorporating a gap-percolation mechanism for handling certain "movement" phenomena, the extended categorial grammars contain special inference rules for treating these problems. The Lambek categorial grammar is one representative of the grammar family under consideration. It allows for a restricted use of hypothetical reasoning. We define a modification of the Cocke-Younger-Kasami (CKY) parsing algorithm which covers this additional deductive power and analyze its time complexity.