{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T01:07:00Z","timestamp":1648602420324},"reference-count":21,"publisher":"MIT Press - Journals","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2016,6]]},"abstract":"<jats:p> The complexity of parsing with synchronous context-free grammars is polynomial in the sentence length for a fixed grammar, but the degree of the polynomial depends on the grammar. Specifically, the degree depends on the length of rules, the permutations represented by the rules, and the parsing strategy adopted to decompose the recognition of a rule into smaller steps. We address the problem of finding the best parsing strategy for a rule, in terms of space and time complexity. We show that it is NP-hard to find the binary strategy with the lowest space complexity. We also show that any algorithm for finding the strategy with the lowest time complexity would imply improved approximation algorithms for finding the treewidth of general graphs. <\/jats:p>","DOI":"10.1162\/coli_a_00246","type":"journal-article","created":{"date-parts":[[2016,4,27]],"date-time":"2016-04-27T18:43:55Z","timestamp":1461782635000},"page":"207-243","source":"Crossref","is-referenced-by-count":0,"title":["Synchronous Context-Free Grammars and Optimal Parsing Strategies"],"prefix":"10.1162","volume":"42","author":[{"given":"Daniel","family":"Gildea","sequence":"first","affiliation":[{"name":"University of Rochester"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giorgio","family":"Satta","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Padova"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0893-9659(95)00015-I"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(69)80006-1"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2007.33.2.201"},{"key":"R7","unstructured":"Crescenzi, Pierluigi, Daniel Gildea, Andrea Marino, Gianluca Rossi, and Giorgio Satta. 2011. Optimal head-driven parsing complexity for linear context-free rewriting systems. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics (ACL-11), pages 450\u2013459. Portland, OR."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.04.003"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060674"},{"key":"R10","unstructured":"Gildea, Daniel. 2010. Optimal parsing strategies for linear context-free rewriting systems. In Proceedings of the 2010 Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL-10), pages 769\u2013776. Los Angeles, CA."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1162\/coli_a_00040"},{"key":"R12","unstructured":"Gildea, Daniel and Daniel \u0160tefankovi\u010d. 2007. Worst-case synchronous grammar rules. In Proceedings of the 2007 Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL-07), pages 147\u2013154. Rochester, NY."},{"key":"R13","unstructured":"Gogate, Vibhav and Rina Dechter. 2004. A complete anytime algorithm for treewidth. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (UAI), pages 201\u2013208."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.3115\/1620754.1620833"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2009.35.4.35406"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90044-2"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2010.06.039"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/321466.321477"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90374-B"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215352"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-40996-3_17"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.3115\/981175.981190"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00246","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:27:51Z","timestamp":1615584471000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/42\/2\/207-243\/1537"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["10.1162\/COLI_a_00246"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00246","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6]]}}}