Elamur Research⌕
☰
home / papers / 2014 / A New Parsing Algorithm for Combinatory Categorial Grammar

A New Parsing Algorithm for Combinatory Categorial Grammar

Paper · 2014 · Marco Kuhlmann and Giorgio Satta

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 PaduaPadua · Italy18 works · 4,260 citations🎓Linköping UniversityLinköping · Sweden18 works · 2,319 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputational Theory and Mathematics · 252 works

🧭 Topics 1Research subjects and languages the work is about.Syntax & grammar formalisms · 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. DOI 10.1162/tacl_a_00192

@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}
}

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
  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
  3. Stephen Clark and James R. Curran. 2007. Wide-coverage efficient statistical parsing with CCG and log-linear models. 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
  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
  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
  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
  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
  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
  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
  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
  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
  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
  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
  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
  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
  17. Blackwell. Mark Steedman. 2000. find
  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
  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
  20. K. Vijay-Shanker and David J. Weir. 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
  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
  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

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kuhlmann-2014-new-parsing-algorithm-combinatory-categorial/