Tractable Parsing for CCGs of Bounded Degree
Bibliographic Data
| ID | 12156162 |
|---|---|
| Authors | Lena Katharina Schiffer (0000-0002-0164-2932, Leipzig University Faculty of Mathematics and Computer Science. [email protected], corresponding author), Marco Kuhlmann (0000-0002-2492-9872, Linköping University Department of Computer and Information Science. [email protected], corresponding author), Giorgio Satta (0000-0001-7742-6438, University of Padua Department of Information Engineering. [email protected], corresponding author) |
| Year | 2022 |
| Volume | 48 |
| Issue | 3 |
| Pages | 593-633 |
| Publication date | 2022-01-01 |
| Open Access | Yes |
| Type | ARTICLE |
| Venue | Computational Linguistics (JOURNAL) |
| Journal identifiers | ISSN: 0891-2017 • E-ISSN: 1530-9312 |
| Publisher | Association for Computational Linguistics (PUBLISHER • US) |
| DOI | 10.1162/coli_a_00441 |
| OpenAlex | W4225968298 |
| Language | EN |
| References cited | 25 |
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
Bounded function · Combinatory categorial grammar · Context (archaeology · Context-free grammar · Degree (music · Emergent grammar · Generative grammar · Grammar · Linguistics · Mildly context-sensitive grammar formalism · Natural language processing · Parsing · Rotation formalisms in three dimensions · Tree-adjoining grammar · Algorithms and Data Compression · Computer Science · Mathematics · Natural Language Processing Techniques · semigroups and automata theory · Artificial Intelligence
| Highly cited | No |
|---|