{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T10:26:37Z","timestamp":1780050397999,"version":"3.53.1"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319299990","type":"print"},{"value":"9783319300009","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-30000-9_41","type":"book-chapter","created":{"date-parts":[[2016,2,25]],"date-time":"2016-02-25T21:45:50Z","timestamp":1456436750000},"page":"533-546","source":"Crossref","is-referenced-by-count":2,"title":["An Error Correcting Parser for Context Free Grammars that Takes Less Than Cubic Time"],"prefix":"10.1007","author":[{"given":"Sanguthevar","family":"Rajasekaran","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marius","family":"Nicolae","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,2,26]]},"reference":[{"issue":"4","key":"41_CR1","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0201022","volume":"1","author":"A Aho","year":"1972","unstructured":"Aho, A., Peterson, T.: A minimum distance error-correcting parser for context-free languages. SIAM J. Comput. 1(4), 305\u2013312 (1972)","journal-title":"SIAM J. Comput."},{"key":"41_CR2","unstructured":"Cocke, J., Schwartz, J.: Programming languages and their compilers: preliminary notes. Courant Institute of Mathematical Sciences, New York University (1970)"},{"issue":"2","key":"41_CR3","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1145\/362007.362035","volume":"13","author":"J Earley","year":"1970","unstructured":"Earley, J.: An efficient context-free parsing algorithm. Commun. ACM 13(2), 94\u2013102 (1970)","journal-title":"Commun. ACM"},{"key":"41_CR4","unstructured":"Gall, F.L.: Powers of tensors and fast matrix multiplication (2014). arXiv:1401.7714"},{"key":"41_CR5","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"2006","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison Wesley, Reading (2006)"},{"key":"41_CR6","unstructured":"Kasami, T.: An efficient recognition and syntax analysis algorithm for context-free languages. Technical report, DTIC Document (1965)"},{"issue":"9","key":"41_CR7","doi-asserted-by":"publisher","first-page":"601","DOI":"10.14778\/2536360.2536361","volume":"6","author":"F Korn","year":"2013","unstructured":"Korn, F., Saha, B., Srivastava, D., Ying, S.: On repairing structural problems in semi-structured data. Proc. VLDB Endowment 6(9), 601\u2013612 (2013)","journal-title":"Proc. VLDB Endowment"},{"issue":"1","key":"41_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/505241.505242","volume":"49","author":"L Lee","year":"2002","unstructured":"Lee, L.: Fast context-free grammar parsing requires fast boolean matrix multiplication. J. ACM 49(1), 1\u201315 (2002)","journal-title":"J. ACM"},{"issue":"2","key":"41_CR9","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0020-0190(95)00007-Y","volume":"54","author":"G Myers","year":"1995","unstructured":"Myers, G.: Approximately matching context-free languages. Inf. Process. Lett. 54(2), 85\u201392 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"41_CR10","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1137\/S009753979326009X","volume":"25","author":"S Rajasekaran","year":"1996","unstructured":"Rajasekaran, S.: Tree-adjoining language parsing in o $$(n^6)$$ ( n 6 ) time. SIAM J. Comput. 25(4), 862\u2013873 (1996)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"41_CR11","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1109\/TCBB.2010.54","volume":"7","author":"S Rajasekaran","year":"2010","unstructured":"Rajasekaran, S., Al Seesi, S., Ammar, R.A.: Improved algorithms for parsing esltags: a grammatical model suitable for rna pseudoknots. IEEE\/ACM Trans. Comput. Biol. Bioinf. (TCBB) 7(4), 619\u2013627 (2010)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf. (TCBB)"},{"key":"41_CR12","unstructured":"Saha, B.: Efficiently computing edit distance to dyck language (2013). arXiv:1311.2557"},{"issue":"2","key":"41_CR13","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"LG Valiant","year":"1975","unstructured":"Valiant, L.G.: General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10(2), 308\u2013315 (1975)","journal-title":"J. Comput. Syst. Sci."},{"key":"41_CR14","doi-asserted-by":"crossref","unstructured":"Williams, R.: Faster all-pairs shortest paths via circuit complexity. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC 2014, pp. 664\u2013673. ACM, New York, NY, USA (2014)","DOI":"10.1145\/2591796.2591811"},{"issue":"2","key":"41_CR15","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0019-9958(67)80007-X","volume":"10","author":"DH Younger","year":"1967","unstructured":"Younger, D.H.: Recognition and parsing of context-free languages in time $$n^3$$ n 3 . Inf. Control 10(2), 189\u2013208 (1967)","journal-title":"Inf. Control"},{"key":"41_CR16","doi-asserted-by":"crossref","unstructured":"Zwick, U.: All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms. In: Proceedings of 39th Annual Symposium on Foundations of Computer Science, pp. 310\u2013319. IEEE (1998)","DOI":"10.1109\/SFCS.1998.743464"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-30000-9_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T14:36:36Z","timestamp":1748788596000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-30000-9_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319299990","9783319300009"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-30000-9_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}