{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T00:54:36Z","timestamp":1648515276799},"reference-count":1,"publisher":"MIT Press - Journals","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p> Bilexical context-free grammars (2-LCFGs) have proved to be accurate models for statistical natural language parsing. Existing dynamic programming algorithms used to parse sentences under these models have running time of O(\u2223w\u2223<jats:sup>4<\/jats:sup>), where w is the input string. <\/jats:p><jats:p> A 2-LCFG is splittable if the left arguments of a lexical head are always independent of the right arguments, and vice versa. When a 2-LCFGs is splittable, parsing time can be asymptotically improved to O(\u2223w\u2223<jats:sup>3<\/jats:sup>). Testing this property is therefore of central interest to parsing efficiency. In this article, however, we show the negative result that splittability of 2-LCFGs is undecidable. <\/jats:p>","DOI":"10.1162\/coli_a_00079","type":"journal-article","created":{"date-parts":[[2011,7,14]],"date-time":"2011-07-14T17:39:41Z","timestamp":1310665181000},"page":"867-879","source":"Crossref","is-referenced-by-count":0,"title":["Splittability of Bilexical Context-Free Grammars is Undecidable"],"prefix":"10.1162","volume":"37","author":[{"given":"Mark-Jan","family":"Nederhof","sequence":"first","affiliation":[{"name":"University of St. Andrews"}]},{"given":"Giorgio","family":"Satta","sequence":"additional","affiliation":[{"name":"University of Padua"}]}],"member":"281","reference":[{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1162\/089120103322753356"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00079","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:27:07Z","timestamp":1615584427000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/37\/4\/867-879\/2127"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":1,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1162\/COLI_a_00079"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00079","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]}}}