Tractable Parsing for CCGs of Bounded Degree

Lena Katharina Schiffer, Marco Kuhlmann, Giorgio Satta


Abstract
Unlike other mildly context-sensitive formalisms, Combinatory Categorial Grammar (CCG) cannot be parsed in polynomial time when the size of the grammar is taken into account. Refining this result, we show that the parsing complexity of CCG is exponential only in the maximum degree of composition. When that degree is fixed, parsing can be carried out in polynomial time. Our finding is interesting from a linguistic perspective because a bounded degree of composition has been suggested as a universal constraint on natural language grammar. Moreover, ours is the first complexity result for a version of CCG that includes substitution rules, which are used in practical grammars but have been ignored in theoretical work.
Anthology ID:
2022.cl-3.4
Volume:
Computational Linguistics, Volume 48, Issue 3 - September 2022
Month:
September
Year:
2022
Address:
Cambridge, MA
Venue:
CL
SIG:
Publisher:
MIT Press
Note:
Pages:
593–633
Language:
URL:
https://aclanthology.org/2022.cl-3.4
DOI:
10.1162/coli_a_00441
Bibkey:
Cite (ACL):
Lena Katharina Schiffer, Marco Kuhlmann, and Giorgio Satta. 2022. Tractable Parsing for CCGs of Bounded Degree. Computational Linguistics, 48(3):593–633.
Cite (Informal):
Tractable Parsing for CCGs of Bounded Degree (Schiffer et al., CL 2022)
Copy Citation:
PDF:
https://aclanthology.org/2022.cl-3.4.pdf
Video:
 https://aclanthology.org/2022.cl-3.4.mp4