{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T14:15:33Z","timestamp":1662041733672},"reference-count":35,"publisher":"MIT Press","issue":"3","license":[{"start":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T00:00:00Z","timestamp":1649289600000},"content-version":"vor","delay-in-days":96,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>","DOI":"10.1162\/coli_a_00441","type":"journal-article","created":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T18:22:02Z","timestamp":1649355722000},"page":"593-633","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":0,"title":["Tractable Parsing for CCGs of Bounded Degree"],"prefix":"10.1162","volume":"48","author":[{"given":"Lena Katharina","family":"Schiffer","sequence":"first","affiliation":[{"name":"Leipzig University Faculty of Mathematics and Computer Science. schiffer@informatik.uni-leipzig.de"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Kuhlmann","sequence":"additional","affiliation":[{"name":"Link\u00f6ping University Department of Computer and Information Science. marco.kuhlmann@liu.se"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giorgio","family":"Satta","sequence":"additional","affiliation":[{"name":"University of Padua Department of Information Engineering. satta@dei.unipd.it"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2022,9,1]]},"reference":[{"key":"2022090113562537600_bib1","unstructured":"Baldridge, Jason\n          . 2002. Lexically Specified Derivational Control in Combinatory Categorial Grammar. Ph.D. thesis, University of Edinburgh, Edinburgh, UK."},{"key":"2022090113562537600_bib2","doi-asserted-by":"publisher","first-page":"211","DOI":"10.3115\/1067807.1067836","article-title":"Multi-modal combinatory categorial grammar","volume-title":"Tenth Conference of the European Chapter of the Association for Computational Linguistics (EACL)","author":"Baldridge","year":"2003"},{"issue":"1","key":"2022090113562537600_bib3","first-page":"1","article-title":"On categorial and phrase-structure grammars","volume":"9F","author":"Bar-Hillel","year":"1960","journal-title":"Bulletin of the Research Council of Israel"},{"key":"2022090113562537600_bib4","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-94-015-6878-4_4","article-title":"Generative power of categorial grammars","volume-title":"Categorial Grammars and Natural Language Structures","author":"Buszkowski","year":"1988"},{"key":"2022090113562537600_bib5","doi-asserted-by":"publisher","first-page":"79","DOI":"10.3115\/981863.981874","article-title":"Efficient normal-form parsing for Combinatory Categorial Grammar","volume-title":"34th Annual Meeting of the Association for Computational Linguistics","author":"Eisner","year":"1996"},{"key":"2022090113562537600_bib6","first-page":"335","article-title":"Accurate context-free parsing with combinatory categorial grammar","volume-title":"Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics","author":"Fowler","year":"2010"},{"issue":"1","key":"2022090113562537600_bib7","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s002249910004","article-title":"Spinal-formed context-free tree grammars","volume":"33","author":"Fujiyoshi","year":"2000","journal-title":"Theory of Computing Systems"},{"key":"2022090113562537600_bib8","doi-asserted-by":"publisher","first-page":"77","DOI":"10.3138\/9781487592769-008","article-title":"Explicit definitions and linguistic dominoes","volume-title":"Systems and Computer Science, Proceedings of the Conference held at Univ. of Western Ontario","author":"Gorn","year":"1965"},{"key":"2022090113562537600_bib9","doi-asserted-by":"publisher","first-page":"335","DOI":"10.3115\/1073083.1073139","article-title":"Generative models for statistical parsing with Combinatory Categorial Grammar","volume-title":"Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics","author":"Hockenmaier","year":"2002"},{"key":"2022090113562537600_bib10","first-page":"41","article-title":"Non-local scrambling: The equivalence of TAG and CCG revisited","volume-title":"Proceedings of the 9th International Workshop Tree Adjoining Grammar and Related Formalisms","author":"Hockenmaier","year":"2008"},{"key":"2022090113562537600_bib11","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1017\/CBO9780511597855.007","article-title":"Tree Adjoining Grammars: How much context-sensitivity is required to provide reasonable structural descriptions?","volume-title":"Natural Language Parsing","author":"Joshi","year":"1985"},{"key":"2022090113562537600_bib12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14846-0","volume-title":"Parsing Beyond Context-Free Grammars","author":"Kallmeyer","year":"2010"},{"key":"2022090113562537600_bib13","doi-asserted-by":"publisher","first-page":"10579","DOI":"10.18653\/v1\/2021.emnlp-main.826","article-title":"A new representation for span-based CCG parsing","volume-title":"Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing","author":"Kato","year":"2021"},{"issue":"3","key":"2022090113562537600_bib14","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/s10849-011-9134-0","article-title":"The equivalence of tree adjoining grammars and monadic linear context-free tree grammars","volume":"20","author":"Kepser","year":"2011","journal-title":"Journal of Logic, Language and Information"},{"key":"2022090113562537600_bib15","first-page":"123","article-title":"Parsing and hypergraphs","volume-title":"Proceedings of the Seventh International Workshop on Parsing Technologies (IWPT-2001)","author":"Klein","year":"2001"},{"key":"2022090113562537600_bib16","doi-asserted-by":"publisher","first-page":"460","DOI":"10.3115\/1609067.1609118","article-title":"Dependency trees and the strong generative capacity of CCG","volume-title":"Proceedings of the 12th EACL","author":"Koller","year":"2009"},{"key":"2022090113562537600_bib17","first-page":"534","article-title":"The importance of rule restrictions in CCG","volume-title":"Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics","author":"Kuhlmann","year":"2010"},{"issue":"2","key":"2022090113562537600_bib18","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1162\/COLI_a_00219","article-title":"Lexicalization and generative power in CCG","volume":"41","author":"Kuhlmann","year":"2015","journal-title":"Computational Linguistics"},{"key":"2022090113562537600_bib19","first-page":"44:1","article-title":"The tree-generative capacity of combinatory categorial grammars","volume-title":"Proceedings of the 39th FSTTCS","author":"Kuhlmann","year":"2019"},{"key":"2022090113562537600_bib20","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.jcss.2021.10.005","article-title":"The tree-generative capacity of combinatory categorial grammars","volume":"124","author":"Kuhlmann","year":"2022","journal-title":"Journal of Computer and System Sciences"},{"issue":"Oct","key":"2022090113562537600_bib21","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1162\/tacl_a_00192","article-title":"A new parsing algorithm for Combinatory Categorial Grammar","volume":"2","author":"Kuhlmann","year":"2014","journal-title":"Transactions of the Association for Computational Linguistics"},{"issue":"3","key":"2022090113562537600_bib22","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1162\/coli_a_00324","article-title":"On the complexity of CCG parsing","volume":"44","author":"Kuhlmann","year":"2018","journal-title":"Computational Linguistics"},{"key":"2022090113562537600_bib23","unstructured":"Schabes, Yves\n          . 1990. Mathematical and Computational Aspects of Lexicalized Grammars. Ph.D. thesis, University of Pennsylvania."},{"key":"2022090113562537600_bib24","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1162\/tacl_a_00393","article-title":"Strong equivalence of TAG and CCG","volume":"9","author":"Schiffer","year":"2021","journal-title":"Transactions of the Association for Computational Linguistics"},{"issue":"3","key":"2022090113562537600_bib25","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF00630917","article-title":"Evidence against the context-freeness of natural language","volume":"8","author":"Shieber","year":"1985","journal-title":"Linguistics and Philosophy"},{"issue":"1\u20132","key":"2022090113562537600_bib26","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0743-1066(95)00035-I","article-title":"Principles and implementation of deductive parsing","volume":"24","author":"Shieber","year":"1995","journal-title":"Journal of Logic Programming"},{"key":"2022090113562537600_bib27","first-page":"228","article-title":"CCG parsing algorithm with incremental tree rotation","volume-title":"Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)","author":"Stanojevi\u0107","year":"2019"},{"issue":"1","key":"2022090113562537600_bib28","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1162\/coli_a_00394","article-title":"Formal basis of a language universal","volume":"47","author":"Stanojevi\u0107","year":"2021","journal-title":"Computational Linguistics"},{"key":"2022090113562537600_bib29","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/6591.001.0001","volume-title":"The Syntactic Process","author":"Steedman","year":"2000"},{"key":"2022090113562537600_bib30","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262017077.001.0001","volume-title":"Taking Scope","author":"Steedman","year":"2011"},{"key":"2022090113562537600_bib31","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1002\/9781444395037.ch5","article-title":"Combinatory Categorial Grammar","volume-title":"Non-Transformational Syntax: Formal and Explicit Models of Grammar","author":"Steedman","year":"2011"},{"key":"2022090113562537600_bib32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.3115\/981823.981824","article-title":"Polynomial time parsing of combinatory categorial grammars","volume-title":"28th Annual Meeting of the Association for Computational Linguistics","author":"Vijay-Shanker","year":"1990"},{"issue":"4","key":"2022090113562537600_bib33","first-page":"591","article-title":"Parsing some constrained grammar formalisms","volume":"19","author":"Vijay-Shanker","year":"1993","journal-title":"Computational Linguistics"},{"issue":"6","key":"2022090113562537600_bib34","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/BF01191624","article-title":"The equivalence of four extensions of context-free grammars","volume":"27","author":"Vijay-Shanker","year":"1994","journal-title":"Mathematical Systems Theory"},{"key":"2022090113562537600_bib35","doi-asserted-by":"publisher","first-page":"278","DOI":"10.3115\/982023.982057","article-title":"Combinatory categorial grammars: Generative power and relationship to linear context-free rewriting systems","volume-title":"Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Weir","year":"1988"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/coli\/article-pdf\/48\/3\/593\/2040364\/coli_a_00441.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/coli\/article-pdf\/48\/3\/593\/2040364\/coli_a_00441.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T13:56:44Z","timestamp":1662040604000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/48\/3\/593\/110441\/Tractable-Parsing-for-CCGs-of-Bounded-Degree"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"references-count":35,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,9,1]]},"published-print":{"date-parts":[[2022,9,1]]}},"URL":"https:\/\/doi.org\/10.1162\/coli_a_00441","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022]]},"published":{"date-parts":[[2022]]}}}