{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T11:21:00Z","timestamp":1648639260064},"reference-count":40,"publisher":"MIT Press - Journals","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p> We present methods for reducing the worst-case and typical-case complexity of a context-free parsing pipeline via hard constraints derived from finite-state pre-processing. We perform O(n) predictions to determine if each word in the input sentence may begin or end a multi-word constituent in chart cells spanning two or more words, or allow single-word constituents in chart cells spanning the word itself. These pre-processing constraints prune the search space for any chart-based parsing algorithm and significantly decrease decoding time. In many cases cell population is reduced to zero, which we term chart cell \u201cclosing.\u201d We present methods for closing a sufficient number of chart cells to ensure provably quadratic or even linear worst-case complexity of context-free inference. In addition, we apply high precision constraints to achieve large typical-case speedups and combine both high precision and worst-case bound constraints to achieve superior performance on both short and long strings. These bounds on processing are achieved without reducing the parsing accuracy, and in some cases accuracy improves. We demonstrate that our method generalizes across multiple grammars and is complementary to other pruning techniques by presenting empirical results for both exact and approximate inference using the exhaustive CKY algorithm, the Charniak parser, and the Berkeley parser. We also report results parsing Chinese, where we achieve the best reported results for an individual model on the commonly reported data set. <\/jats:p>","DOI":"10.1162\/coli_a_00109","type":"journal-article","created":{"date-parts":[[2012,3,16]],"date-time":"2012-03-16T15:06:50Z","timestamp":1331910410000},"page":"719-753","source":"Crossref","is-referenced-by-count":0,"title":["Finite-State Chart Constraints for Reduced Complexity Context-Free Parsing Pipelines"],"prefix":"10.1162","volume":"38","author":[{"given":"Brian","family":"Roark","sequence":"first","affiliation":[{"name":"Oregon Health & Science University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kristy","family":"Hollingshead","sequence":"additional","affiliation":[{"name":"University of Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Bodenstab","sequence":"additional","affiliation":[{"name":"Oregon Health & Science University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"R1","first-page":"237","volume":"25","author":"Bangalore Srinivas","year":"1999","journal-title":"Computational Linguistics"},{"key":"R2","first-page":"53","volume-title":"Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010)","author":"Bergsma Shane","year":"2010"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.3115\/112405.112467"},{"key":"R4","first-page":"440","volume-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics","author":"Bodenstab Nathan","year":"2011"},{"key":"R5","first-page":"676","volume-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics","author":"Bodenstab Nathan","year":"2011"},{"key":"R6","first-page":"127","volume-title":"Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics","author":"Burkett David","year":"2010"},{"key":"R7","first-page":"275","volume":"24","author":"Caraballo Sharon A.","year":"1997","journal-title":"Computational Linguistics"},{"key":"R8","first-page":"132","volume-title":"Proceedings of the 1st Conference of the North American Chapter of the Association for Computational Linguistics","author":"Charniak Eugene","year":"2000"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.3115\/1219840.1219862"},{"key":"R10","first-page":"200","volume-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies","author":"Cherry Colin","year":"2011"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.3115\/1220355.1220396"},{"key":"R12","volume-title":"Programming languages and their compilers: Preliminary notes.","author":"Cocke John","year":"1970"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.3115\/1118693.1118694"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.3115\/1621410.1621416"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.3115\/1596276.1596314"},{"key":"R16","volume-title":"Reducing the grammar constant: an analysis of CYK parsing efficiency. Technical report CSLU-2010-02","author":"Dunlop Aaron","year":"2010"},{"key":"R17","first-page":"163","volume-title":"Proceedings of the 12th International Conference on Parsing Technologies (IWPT)","author":"Dunlop Aaron","year":"2011"},{"issue":"8","key":"R18","first-page":"451","volume":"6","author":"Earley Jay","year":"1970","journal-title":"Communications of the ACM"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.3115\/1654494.1654498"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.3115\/1273073.1273111"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.3115\/1220575.1220674"},{"key":"R22","first-page":"952","volume-title":"Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Hollingshead Kristy","year":"2007"},{"key":"R23","volume-title":"An efficient recognition and syntax analysis algorithm for context-free languages. Technical report AFCRL-65-758","author":"Kasami Tadao","year":"1965"},{"key":"R24","first-page":"313","volume":"19","author":"Marcus Mitchell P.","year":"1993","journal-title":"Computational Linguistics"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.3115\/1220575.1220641"},{"key":"R26","first-page":"73","volume-title":"Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics (EACL)","author":"Nivre Joakim","year":"2006"},{"key":"R27","first-page":"404","volume-title":"Proceedings of Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics (HLT-NAACL)","author":"Petrov Slav","year":"2007"},{"key":"R28","first-page":"1663","volume-title":"Proceedings of the 22nd National Conference on Artificial Intelligence - Volume 2","author":"Petrov Slav","year":"2007"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007502103375"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.3115\/1599081.1599175"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.3115\/1620754.1620849"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.3115\/1073445.1073473"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.3115\/1697236.1697276"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.3115\/1613715.1613739"},{"key":"R35","first-page":"2415","volume-title":"Proceedings of NIPS","author":"Weiss David","year":"2010"},{"key":"R36","first-page":"916","volume":"9","author":"Weiss David","year":"2010","journal-title":"Journal of Machine Learning Research - Proceedings Track"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1017\/S135132490400364X"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)80007-X"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.3115\/1699648.1699702"},{"key":"R40","first-page":"1472","volume-title":"Proceedings of the 23rd International Conference on Computational Linguistics","author":"Zhang Yue","year":"2010"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00109","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:27:14Z","timestamp":1615584434000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/38\/4\/719-753\/2158"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1162\/COLI_a_00109"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00109","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12]]}}}