---
title: "A New Parsing Algorithm for Combinatory Categorial Grammar"
description: "Kuhlmann and Satta propose an alternative recognizer. 23 references, cited by 7 papers here."
authors: ["Marco Kuhlmann", "Giorgio Satta"]
year: 2014
venue: "Transactions of the Association for Computational Linguistics"
source: "https://aclanthology.org/Q14-1032/"
doi: "10.1162/tacl_a_00192"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/kuhlmann-2014-new-parsing-algorithm-combinatory-categorial/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/kuhlmann-2014-new-parsing-algorithm-combinatory-categorial/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2014](https://md.research.elamur.ai/free/en/papers/2014/page/3/) / A New Parsing Algorithm for Combinatory Categorial Grammar

# A New Parsing Algorithm for Combinatory Categorial Grammar

**Authors:** [Marco Kuhlmann](https://md.research.elamur.ai/free/en/authors/marco-kuhlmann/) and [Giorgio Satta](https://md.research.elamur.ai/free/en/authors/giorgio-satta/) · **Year:** 2014 · **Venue:** [Transactions of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/tacl/) ([Transactions of the Association for Computational Linguistics (TACL) 2014](https://md.research.elamur.ai/free/en/venues/tacl/2014/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/Q14-1032/) · [PDF](https://aclanthology.org/Q14-1032.pdf) · [DOI 10.1162/tacl\_a\_00192](https://doi.org/10.1162/tacl_a_00192) · [OpenAlex](https://openalex.org/W2114282531)

**Citations:** 13 citations (OpenAlex, 2026-10-14) · 7 in our library, of the 149,439 papers whose bibliographies we read

## Summary
Combinatory Categorial Grammar (CCG) is a lexicalized, mildly context-sensitive formalism used for parsing, semantic construction and machine translation. Before this paper, the only published polynomial-time parser for CCG was the V&W algorithm by Vijay-Shanker and Weir (1993). That algorithm is intricate and has not been adopted in practical parsers. Kuhlmann and Satta propose an alternative recognizer.

They start from a naive CKY-style deduction system. This system can become exponential once composition rules of degree 2 or higher allow category arity to grow with sentence length. To fix this, the authors cap the arity of ordinary items by a grammar constant. They add a second item type for derivation contexts: gapped fragments that never access the lower part of the primary category's argument stack, so they can be shared across any such stack. Unlike V&W, contexts may have an empty excess, which removes several case distinctions.

The result has only three forward inference rules, runs directly in O(n^6), and comes with a simpler correctness proof. This makes polynomial CCG parsing easier to implement and verify. The work is purely theoretical and reports no experiments.

## Key points
- The new algorithm matches the O(n^6) bound of the V&W algorithm. V&W naturally runs in O(n^7) and needs extra bookkeeping to reach O(n^6).
- It uses 3 forward inference rules with at most 2 antecedents each. V&W uses 9 rules, some with 3 antecedents.
- The baseline is a CKY-style generalization of Shieber et al. (1995). It is cubic for grammars with rule degree ≤ 1 (context-free power) but exponential in general.
- The paper discusses several extensions:
  - rule restrictions;
  - multi-modal CCG, via the translation of Baldridge and Kruijff (2003);
  - type-raising, assuming a finite set of instances;
  - substitution, at the cost of spurious ambiguity.
- Only a recognizer is specified; a derivation forest can be obtained with backpointers. Runtime is exponential in grammar size, and whether CCG parsing is polynomial with the grammar as part of the input is left open.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [University of Padua](https://md.research.elamur.ai/free/en/universities/university-of-padua/) — University, Padua, Italy · 18 works · 4,260 citations
- [Linköping University](https://md.research.elamur.ai/free/en/universities/linkoping-university/) — University, Linköping, Sweden · 18 works · 2,319 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 252 works

🧭 Topics (1): [📐 Syntax & grammar formalisms](https://md.research.elamur.ai/free/en/topics/syntax-grammar/) · 214 works

## Cite

Cite as: Marco Kuhlmann and Giorgio Satta. 2014. A New Parsing Algorithm for Combinatory Categorial Grammar. Transactions of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@article{kuhlmann2014new,
  title = {{A New Parsing Algorithm for Combinatory Categorial Grammar}},
  author = {Marco Kuhlmann and Giorgio Satta},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2014},
  doi = {10.1162/tacl\_a\_00192},
  url = {https://doi.org/10.1162/tacl_a_00192}
}
```

- [← previous A Hybrid Approach to Features Representation for Fine-grained Arabic Named Entity Recognition](https://md.research.elamur.ai/free/en/papers/alotaibi-2014-hybrid-approach-features-representation-fine/)
- [next → An Arabizi-English social media statistical machine translation system](https://md.research.elamur.ai/free/en/papers/may-2014-arabizi-english-social-media-statistical/)
- [↑ back to papers of 2014](https://md.research.elamur.ai/free/en/papers/2014/page/3/)

## References

23 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Jason Baldridge and Geert-Jan M. Kruijff. 2003. Multimodal combinatory categorial grammar. In Tenth Conference of the European Chapter of the Association for Computational Linguistics (EACL), pages 211–218, Budapest, Hungary. [find](https://scholar.google.com/scholar?q=Jason+Baldridge+and+Geert%2DJan+M%2E+Kruijff%2E+2003%2E+Multimodal+combinatory+categorial+grammar%2E+In+Tenth+Conference+of+the+European+Chapter+of+the+Association+for+Computational+Linguistics+%28EACL%29%2C+pages+21)
2. Johan Bos, Stephen Clark, Mark Steedman, James R. Curran, and Julia Hockenmaier. 2004. Wide-coverage semantic representations from a CCG parser. In Proceedings of the 20th International Conference on Computational Linguistics (COLING), pages 1240–1246, Geneva, Switzerland. [find](https://scholar.google.com/scholar?q=Johan+Bos%2C+Stephen+Clark%2C+Mark+Steedman%2C+James+R%2E+Curran%2C+and+Julia+Hockenmaier%2E+2004%2E+Wide%2Dcoverage+semantic+representations+from+a+CCG+parser%2E+In+Proceedings+of+the+20th+International+Conference+on+)
3. Stephen Clark and James R. Curran. 2007. [Wide-coverage efficient statistical parsing with CCG and log-linear models](https://md.research.elamur.ai/free/en/papers/clark-2007-wide-coverage-efficient-statistical-parsing/). Computational Linguistics, 33(4):493– 552.
4. Timothy Fowler and Gerald Penn. 2010. Accurate context-free parsing with combinatory categorial grammar. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL), pages 335–344, Uppsala, Sweden. [find](https://scholar.google.com/scholar?q=Timothy+Fowler+and+Gerald+Penn%2E+2010%2E+Accurate+context%2Dfree+parsing+with+combinatory+categorial+grammar%2E+In+Proceedings+of+the+48th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL)
5. Julia Hockenmaier and Peter Young. 2008. Non-local scrambling: The equivalence of TAG and CCG revisited. In Ninth International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+), Tübingen, Germany. [find](https://scholar.google.com/scholar?q=Julia+Hockenmaier+and+Peter+Young%2E+2008%2E+Non%2Dlocal+scrambling%3A+The+equivalence+of+TAG+and+CCG+revisited%2E+In+Ninth+International+Workshop+on+Tree+Adjoining+Grammars+and+Related+Formalisms+%28TAG%2B%29%2C+T%C3%BCbin)
6. Aravind K. Joshi and Yves Schabes. 1997. Tree-Adjoining Grammars. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, volume 3, pages 69–123. [find](https://scholar.google.com/scholar?q=Aravind+K%2E+Joshi+and+Yves+Schabes%2E+1997%2E+Tree%2DAdjoining+Grammars%2E+In+Grzegorz+Rozenberg+and+Arto+Salomaa%2C+editors%2C+Handbook+of+Formal+Languages%2C+volume+3%2C+pages+69%E2%80%93123%2E)
7. Springer. Aravind K. Joshi. 1985. Tree Adjoining Grammars: How much context-sensitivity is required to provide reasonable structural descriptions? In David R. Dowty, Lauri Karttunen, and Arnold M. Zwicky, editors, Natural Language Parsing, pages 206–250. [find](https://scholar.google.com/scholar?q=Springer%2E+Aravind+K%2E+Joshi%2E+1985%2E+Tree+Adjoining+Grammars%3A+How+much+context%2Dsensitivity+is+required+to+provide+reasonable+structural+descriptions%3F+In+David+R%2E+Dowty%2C+Lauri+Karttunen%2C+and+Arnold+M%2E+Zwi)
8. Cambridge University Press. Alexander Koller and Marco Kuhlmann. 2009. Dependency trees and the strong generative capacity of CCG. In Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics (EACL), pages 460–468, Athens, Greece. [find](https://scholar.google.com/scholar?q=Cambridge+University+Press%2E+Alexander+Koller+and+Marco+Kuhlmann%2E+2009%2E+Dependency+trees+and+the+strong+generative+capacity+of+CCG%2E+In+Proceedings+of+the+12th+Conference+of+the+European+Chapter+of+the+)
9. Marco Kuhlmann, Alexander Koller, and Giorgio Satta. 2010. The importance of rule restrictions in CCG. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL), pages 534–543, Uppsala, Sweden. [find](https://scholar.google.com/scholar?q=Marco+Kuhlmann%2C+Alexander+Koller%2C+and+Giorgio+Satta%2E+2010%2E+The+importance+of+rule+restrictions+in+CCG%2E+In+Proceedings+of+the+48th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%29%2C)
10. Tom Kwiatkowski, Luke Zettlemoyer, Sharon Goldwater, and Mark Steedman. 2010. Inducing probabilistic CCG grammars from logical form with higher-order unification. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1223–1233, Cambridge, MA, USA. [find](https://scholar.google.com/scholar?q=Tom+Kwiatkowski%2C+Luke+Zettlemoyer%2C+Sharon+Goldwater%2C+and+Mark+Steedman%2E+2010%2E+Inducing+probabilistic+CCG+grammars+from+logical+form+with+higher%2Dorder+unification%2E+In+Proceedings+of+the+2010+Conference)
11. Bernard Lang. 1974. Deterministic techniques for efficient non-deterministic parsers. In Jacques Loecx, editor, Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken, July 29–August 2, 1974, number 14 in Lecture Notes in Computer Science, pages 255–269. [find](https://scholar.google.com/scholar?q=Bernard+Lang%2E+1974%2E+Deterministic+techniques+for+efficient+non%2Ddeterministic+parsers%2E+In+Jacques+Loecx%2C+editor%2C+Automata%2C+Languages+and+Programming%2C+2nd+Colloquium%2C+University+of+Saarbr%C3%BCcken%2C+July+29%E2%80%93)
12. Springer. Mike Lewis and Mark Steedman. 2013. Combined distributional and logical semantics. Transactions of the Association for Computational Linguistics, 1(May):179– 192. [find](https://scholar.google.com/scholar?q=Springer%2E+Mike+Lewis+and+Mark+Steedman%2E+2013%2E+Combined+distributional+and+logical+semantics%2E+Transactions+of+the+Association+for+Computational+Linguistics%2C+1%28May%29%3A179%E2%80%93+192%2E)
13. Mark-Jan Nederhof and Giorgio Satta. 2004. Tabular parsing. In Carlos Martín-Vide, Victor Mitrana, and Gheorghe Păun, editors, Formal Languages and Applications, volume 148 of Studies in Fuzziness and Soft Computing, pages 529–549. [find](https://scholar.google.com/scholar?q=Mark%2DJan+Nederhof+and+Giorgio+Satta%2E+2004%2E+Tabular+parsing%2E+In+Carlos+Mart%C3%ADn%2DVide%2C+Victor+Mitrana%2C+and+Gheorghe+Pa%CC%86un%2C+editors%2C+Formal+Languages+and+Applications%2C+volume+148+of+Studies+in+Fuzziness+an)
14. Springer. Remo Pareschi and Mark Steedman. 1987. A lazy way to chart-parse with categorial grammars. In Proceedings of the 25th Annual Meeting of the Association for Computational Linguistics (ACL), pages 81–88, Stanford, CA, USA. [find](https://scholar.google.com/scholar?q=Springer%2E+Remo+Pareschi+and+Mark+Steedman%2E+1987%2E+A+lazy+way+to+chart%2Dparse+with+categorial+grammars%2E+In+Proceedings+of+the+25th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%29%2C+p)
15. Stuart M. Shieber, Yves Schabes, and Fernando Pereira. 1995. Principles and implementation of deductive parsing. Journal of Logic Programming, 24(1–2):3–36. [find](https://scholar.google.com/scholar?q=Stuart+M%2E+Shieber%2C+Yves+Schabes%2C+and+Fernando+Pereira%2E+1995%2E+Principles+and+implementation+of+deductive+parsing%2E+Journal+of+Logic+Programming%2C+24%281%E2%80%932%29%3A3%E2%80%9336%2E)
16. Mark Steedman and Jason Baldridge. 2011. Combinatory categorial grammar. In Robert D. Borsley and Kersti Börjars, editors, Non-Transformational Syntax: Formal and Explicit Models of Grammar, chapter 5, pages 181– 224. [find](https://scholar.google.com/scholar?q=Mark+Steedman+and+Jason+Baldridge%2E+2011%2E+Combinatory+categorial+grammar%2E+In+Robert+D%2E+Borsley+and+Kersti+B%C3%B6rjars%2C+editors%2C+Non%2DTransformational+Syntax%3A+Formal+and+Explicit+Models+of+Grammar%2C+chapter+5)
17. Blackwell. Mark Steedman. 2000. [find](https://scholar.google.com/scholar?q=Blackwell%2E+Mark+Steedman%2E+2000%2E)
18. The Syntactic Process. MIT Press. Masaru Tomita. 1988. Graph-structured stack and natural language parsing. In Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics (ACL), pages 249–257, Buffalo, USA. [find](https://scholar.google.com/scholar?q=The+Syntactic+Process%2E+MIT+Press%2E+Masaru+Tomita%2E+1988%2E+Graph%2Dstructured+stack+and+natural+language+parsing%2E+In+Proceedings+of+the+26th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28)
19. K. Vijay-Shanker and David J. Weir. 1990. Polynomial time parsing of combinatory categorial grammars. In Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1–8, Pittsburgh, USA. [find](https://scholar.google.com/scholar?q=K%2E+Vijay%2DShanker+and+David+J%2E+Weir%2E+1990%2E+Polynomial+time+parsing+of+combinatory+categorial+grammars%2E+In+Proceedings+of+the+28th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%29%2C+)
20. K. Vijay-Shanker and David J. Weir. 1993. [Parsing some constrained grammar formalisms](https://md.research.elamur.ai/free/en/papers/shanker-1993-parsing-some-constrained-grammar-formalisms/). Computational Linguistics, 19(4):591–636.
21. K. Vijay-Shanker and David J. Weir. 1994. The equivalence of four extensions of context-free grammars. Mathematical Systems Theory, 27(6):511–546. [find](https://scholar.google.com/scholar?q=K%2E+Vijay%2DShanker+and+David+J%2E+Weir%2E+1994%2E+The+equivalence+of+four+extensions+of+context%2Dfree+grammars%2E+Mathematical+Systems+Theory%2C+27%286%29%3A511%E2%80%93546%2E)
22. Jonathan Weese, Chris Callison-Burch, and Adam Lopez. 2012. Using categorial grammar to label translation rules. In Proceedings of the Seventh Workshop on Statistical Machine Translation, pages 222–231, Montréal, Canada. [find](https://scholar.google.com/scholar?q=Jonathan+Weese%2C+Chris+Callison%2DBurch%2C+and+Adam+Lopez%2E+2012%2E+Using+categorial+grammar+to+label+translation+rules%2E+In+Proceedings+of+the+Seventh+Workshop+on+Statistical+Machine+Translation%2C+pages+222%E2%80%9323)
23. David J. Weir and Aravind K. Joshi. 1988. Combinatory categorial grammars: Generative power and relationship to linear context-free rewriting systems. In Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics (ACL), pages 278–285, Buffalo, USA. [find](https://scholar.google.com/scholar?q=David+J%2E+Weir+and+Aravind+K%2E+Joshi%2E+1988%2E+Combinatory+categorial+grammars%3A+Generative+power+and+relationship+to+linear+context%2Dfree+rewriting+systems%2E+In+Proceedings+of+the+26th+Annual+Meeting+of+the+)

*Updated 30 October 2026*