{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T03:24:55Z","timestamp":1762917895964,"version":"3.41.0"},"reference-count":35,"publisher":"MIT Press","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2018,9]]},"abstract":"<jats:p>We study the parsing complexity of Combinatory Categorial Grammar (CCG) in the formalism of Vijay-Shanker and Weir ( 1994 ). As our main result, we prove that any parsing algorithm for this formalism will take in the worst case exponential time when the size of the grammar, and not only the length of the input sentence, is included in the analysis. This sets the formalism of Vijay-Shanker and Weir ( 1994 ) apart from weakly equivalent formalisms such as Tree Adjoining Grammar, for which parsing can be performed in time polynomial in the combined size of grammar and input sentence. Our results contribute to a refined understanding of the class of mildly context-sensitive grammars, and inform the search for new, mildly context-sensitive versions of CCG.<\/jats:p>","DOI":"10.1162\/coli_a_00324","type":"journal-article","created":{"date-parts":[[2018,6,7]],"date-time":"2018-06-07T18:53:10Z","timestamp":1528397590000},"page":"447-482","source":"Crossref","is-referenced-by-count":7,"title":["On the Complexity of CCG Parsing"],"prefix":"10.1162","volume":"44","author":[{"given":"Marco","family":"Kuhlmann","sequence":"first","affiliation":[{"name":"Link\u00f6ping University, Department of Computer and Information Science."}]},{"given":"Giorgio","family":"Satta","sequence":"additional","affiliation":[{"name":"University of Padua, Department of Information Engineering."}]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[{"name":"Link\u00f6ping University, Department of Computer and Information Science."}]}],"member":"281","reference":[{"unstructured":"Baldridge, Jason. 2002. Lexically Specified Derivational Control in Combinatory Categorial Grammar. Ph.D. thesis, University of Edinburgh.","key":"bib1"},{"doi-asserted-by":"publisher","key":"bib2","DOI":"10.3115\/1067807.1067836"},{"doi-asserted-by":"publisher","key":"bib3","DOI":"10.1145\/322234.322243"},{"doi-asserted-by":"publisher","key":"bib4","DOI":"10.1162\/coli.2007.33.4.493"},{"key":"bib5","first-page":"69","volume-title":"Natural Language Parsing and Linguistic Theories","author":"Gazdar Gerald","year":"1987"},{"key":"bib6","first-page":"276","volume-title":"Proceedings of Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics","author":"G\u00f3mez-Rodr\u00edguez Carlos","year":"2010"},{"doi-asserted-by":"publisher","key":"bib7","DOI":"10.1137\/0209010"},{"doi-asserted-by":"publisher","key":"bib8","DOI":"10.1162\/coli.2007.33.3.355"},{"doi-asserted-by":"publisher","key":"bib9","DOI":"10.1007\/s00224-009-9246-y"},{"doi-asserted-by":"publisher","key":"bib10","DOI":"10.1017\/CBO9780511597855.007"},{"doi-asserted-by":"publisher","key":"bib11","DOI":"10.1007\/978-3-642-59126-6_2"},{"issue":"1","key":"bib12","first-page":"78","volume":"75","author":"Kaji Yuichi","year":"1992","journal-title":"IEICE Transactions on Information and Systems"},{"doi-asserted-by":"publisher","key":"bib13","DOI":"10.1162\/COLI_a_00219"},{"doi-asserted-by":"publisher","key":"bib14","DOI":"10.1162\/tacl_a_00192"},{"doi-asserted-by":"publisher","key":"bib15","DOI":"10.18653\/v1\/D16-1262"},{"key":"bib16","doi-asserted-by":"crossref","first-page":"681","DOI":"10.18653\/v1\/D13-1064","volume-title":"Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing","author":"Lewis Mike","year":"2013"},{"doi-asserted-by":"publisher","key":"bib17","DOI":"10.3115\/v1\/D14-1107"},{"doi-asserted-by":"publisher","key":"bib18","DOI":"10.3115\/981175.981191"},{"volume-title":"Computational Complexity","year":"1994","author":"Papadimitriou Christos H.","key":"bib19"},{"doi-asserted-by":"publisher","key":"bib20","DOI":"10.3115\/1699571.1699619"},{"doi-asserted-by":"publisher","key":"bib21","DOI":"10.3115\/981131.981137"},{"doi-asserted-by":"publisher","key":"bib22","DOI":"10.3115\/981967.981979"},{"unstructured":"Schabes, Yves. 1990. Mathematical and Computational Aspects of Lexicalized Grammars. Ph.D. thesis, University of Pennsylvania, Philadelphia.","key":"bib23"},{"doi-asserted-by":"publisher","key":"bib24","DOI":"10.1016\/0304-3975(91)90374-B"},{"key":"bib25","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6591.001.0001","volume-title":"The Syntactic Process","author":"Steedman Mark","year":"2000"},{"doi-asserted-by":"publisher","key":"bib26","DOI":"10.1002\/9781444395037.ch5"},{"doi-asserted-by":"publisher","key":"bib27","DOI":"10.3115\/981210.981221"},{"doi-asserted-by":"publisher","key":"bib28","DOI":"10.3115\/981823.981824"},{"issue":"4","key":"bib29","first-page":"591","volume":"19","author":"Vijay-Shanker K.","year":"1993","journal-title":"Computational Linguistics"},{"doi-asserted-by":"publisher","key":"bib30","DOI":"10.1007\/BF01191624"},{"doi-asserted-by":"publisher","key":"bib31","DOI":"10.3115\/981175.981190"},{"doi-asserted-by":"publisher","key":"bib32","DOI":"10.3115\/982023.982057"},{"doi-asserted-by":"publisher","key":"bib33","DOI":"10.1162\/coli.09-023-R1-08-002"},{"key":"bib34","first-page":"683","volume-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics","author":"Zhang Yue","year":"2011"},{"doi-asserted-by":"publisher","key":"bib35","DOI":"10.1162\/COLI_a_00229"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/coli_a_00324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T01:12:42Z","timestamp":1751677962000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/44\/3\/447-482\/1606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["10.1162\/coli_a_00324"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00324","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"type":"print","value":"0891-2017"},{"type":"electronic","value":"1530-9312"}],"subject":[],"published":{"date-parts":[[2018,9]]}}}