{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:42:18Z","timestamp":1777596138579,"version":"3.51.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,6,6]],"date-time":"2016-06-06T00:00:00Z","timestamp":1465171200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003125","name":"Suomen Kulttuurirahasto","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003125","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s00224-016-9683-3","type":"journal-article","created":{"date-parts":[[2016,6,5]],"date-time":"2016-06-05T22:26:34Z","timestamp":1465165594000},"page":"581-605","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Generalized LR Parsing Algorithm for Grammars with One-Sided Contexts"],"prefix":"10.1007","volume":"61","author":[{"given":"Mikhail","family":"Barash","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,6]]},"reference":[{"key":"9683_CR1","first-page":"345","volume":"6651","author":"T Aizikowitz","year":"2011","unstructured":"Aizikowitz, T., Kaminski, M.: LR(0) Conjunctive grammars and deterministic synchronized alternating pushdown automata, Computer Science in Russia (CSR 2011, St. Petersburg, Russia). LNCS 6651, 345\u2013358 (2011)","journal-title":"LNCS"},{"issue":"9","key":"9683_CR2","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1007\/PL00013319","volume":"37","author":"J Aycock","year":"2001","unstructured":"Aycock, J., Horspool, R.N., Janou\u0161ek, J., Melichar, B.: Even faster generalized LR parsing. Acta Informatica 37(9), 633\u2013651 (2001)","journal-title":"Acta Informatica"},{"key":"9683_CR3","unstructured":"Barash, M.: Programming language specification by a grammar with contexts. NCMA 2013 (Ume\u00e5, Sweden, 13\u201314, August 2013, 51\u201367"},{"key":"9683_CR4","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1016\/j.ic.2014.03.003","volume":"237","author":"M Barash","year":"2014","unstructured":"Barash, M., Okhotin, A.: An extension of context-free grammars with one-sided context specifications. Inf. Comput. 237, 268\u2013293 (2014)","journal-title":"Inf. Comput."},{"key":"9683_CR5","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.tcs.2015.05.004","volume":"591","author":"M Barash","year":"2015","unstructured":"Barash, M., Okhotin, A.: Two-sided context specifications in formal grammars. Theor. Comput. Sci. 591, 134\u2013153 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9683_CR6","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1051\/ita\/2015004","volume":"49","author":"M Barash","year":"2015","unstructured":"Barash, M., Okhotin, A.: Linear grammars with one-sided contexts and their automaton representation. RAIRO Informatique Th\u00e9orique et Applications 49(2), 153\u2013178 (2015)","journal-title":"RAIRO Informatique Th\u00e9orique et Applications"},{"key":"9683_CR7","first-page":"2707","volume":"11","author":"A Clark","year":"2010","unstructured":"Clark, A., Eyraud, R., Habrard, A.: Using contextual representations to efficiently learn context-free languages. J. Mach. Learn. Res. 11, 2707\u20132744 (2010)","journal-title":"J. Mach. Learn. Res."},{"key":"9683_CR8","doi-asserted-by":"crossref","unstructured":"Economopoulos, G., Klint, P., Vinju, J.: Faster scannerless GLR parsing. Compiler Construction (CC 2009, York, United Kingdom, March 22\u201329, 2009) LNCS 5501, 126\u2013141","DOI":"10.1007\/978-3-642-00722-4_10"},{"key":"9683_CR9","doi-asserted-by":"crossref","unstructured":"Kallmeyer, L., Maier, W.: LR Parsing for LCFRS. Human Language Technologies (NAACL HLT 2015, Denver, Colorado, USA, 31 May\u20135 June 2015), 1250\u20131255","DOI":"10.3115\/v1\/N15-1134"},{"key":"9683_CR10","doi-asserted-by":"crossref","unstructured":"Kipps, J.R.: GLR parsing in time \ud835\udcde ( n 3 ) $\\mathcal {O}(n^{3})$ . In: Tomita, M. (ed.) Generalized LR Parsing, Kluwer, pp 43\u201359 (1991)","DOI":"10.1007\/978-1-4615-4034-2_4"},{"key":"9683_CR11","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/S0019-9958(65)90426-2","volume":"8","author":"DE Knuth","year":"1965","unstructured":"Knuth, D.E.: On the translation of languages from left to right. Inf. Control. 8, 607\u2013639 (1965)","journal-title":"Inf. Control."},{"key":"9683_CR12","volume-title":"Logic for Problem Solving","author":"R Kowalski","year":"1979","unstructured":"Kowalski, R.: Logic for Problem Solving. North-Holland, Amsterdam (1979)"},{"key":"9683_CR13","doi-asserted-by":"crossref","unstructured":"Lang, B.: Deterministic techniques for efficient non-deterministic parsers. Automata, Languages and Programming (ICALP 1974, Saarbr\u00fccken, Germany, July 29\u2013August 2, 1974), LNCS 14, 255\u2013 269","DOI":"10.1007\/3-540-06841-4_65"},{"key":"9683_CR14","doi-asserted-by":"crossref","unstructured":"Nederhof, M.-J.: An alternative LR algorithm for TAGs. 36th Annual Meeting of the Association for Computational Linguistics (COLING-ACL\u201998, Montr\u00e9al, Canada, 10\u201314 August 1998), 946\u2013952","DOI":"10.3115\/980691.980725"},{"issue":"4","key":"9683_CR15","first-page":"519","volume":"6","author":"A Okhotin","year":"2001","unstructured":"Okhotin, A.: Conjunctive grammars. Journal of Automata, Languages and Combinatorics 6(4), 519\u2013535 (2001)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"9683_CR16","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1023\/A:1016329527130","volume":"5","author":"A Okhotin","year":"2002","unstructured":"Okhotin, A.: LR Parsing for conjunctive grammars. Grammars 5, 81\u2013124 (2002)","journal-title":"Grammars"},{"issue":"3","key":"9683_CR17","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1142\/S0129054106004029","volume":"17","author":"A Okhotin","year":"2006","unstructured":"Okhotin, A.: Generalized LR parsing algorithm for Boolean grammars. Int. J. Found. Comput. Sci. 17(3), 629\u2013664 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9683_CR18","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2013.06.001","volume":"9","author":"A Okhotin","year":"2013","unstructured":"Okhotin, A.: Conjunctive and Boolean grammars: the true general case of the context-free grammars. Computer Science Review 9, 27\u201359 (2013)","journal-title":"Computer Science Review"},{"key":"9683_CR19","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/j.tcs.2013.09.011","volume":"516","author":"A Okhotin","year":"2014","unstructured":"Okhotin, A.: Parsing by matrix multiplication generalized to Boolean grammars. Theor. Comput. Sci. 516, 101\u2013120 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"9683_CR20","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/j.tcs.2015.03.041","volume":"588","author":"A Okhotin","year":"2015","unstructured":"Okhotin, A.: Improved normal form for grammars with one-sided contexts. Theor. Comput. Sci. 588, 52\u201372 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"9683_CR21","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/j.tcs.2016.01.007","volume":"618","author":"A Okhotin","year":"2016","unstructured":"Okhotin, A.: Input-driven languages are linear conjunctive. Theor. Comput. Sci. 618, 52\u201371 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"9683_CR22","doi-asserted-by":"crossref","unstructured":"Pereira, F.C.N., Warren, D.H.D.: Parsing as deduction. 21st Annual Meeting of the Association for Computational Linguistics (ACL 1983, Cambridge, Mass., USA, 15\u201317 June 1983), 137\u2013144","DOI":"10.3115\/981311.981338"},{"key":"9683_CR23","doi-asserted-by":"crossref","unstructured":"Prolo, C.A.: An efficient LR parser generator for tree-adjoining grammars. In: Bunt, H., Caroll, J., Satta, G. (eds.) New Developments in Parsing Technology, pp 125\u2013155 (2005)","DOI":"10.1007\/1-4020-2295-6_7"},{"key":"9683_CR24","doi-asserted-by":"crossref","unstructured":"Rabkin, M.: Recognizing two-sided contexts in cubic time. Computer Science\u2014Theory and Applications (CSR 2014, Moscow, Russia, 6\u201312, June 2014), LNCS 8476, 14\u2013324","DOI":"10.1007\/978-3-319-06686-8_24"},{"issue":"4","key":"9683_CR25","first-page":"1","volume":"14","author":"WC Rounds","year":"1988","unstructured":"Rounds, W.C.: LFP: A logic for linguistic descriptions and an analysis of its complexity. Computational Linguistics 14(4), 1\u20139 (1988)","journal-title":"Computational Linguistics"},{"issue":"4","key":"9683_CR26","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1145\/1146809.1146810","volume":"28","author":"E Scott","year":"2006","unstructured":"Scott, E., Johnstone, A.: Right nulled GLR parsers. ACM Trans. Program. Lang. Syst. 28(4), 577\u2013618 (2006)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"9683_CR27","doi-asserted-by":"crossref","unstructured":"Tomita, M.: Efficient Parsing for Natural Language. Kluwer (1986)","DOI":"10.1007\/978-1-4757-1885-0"},{"issue":"1","key":"9683_CR28","first-page":"31","volume":"13","author":"M Tomita","year":"1987","unstructured":"Tomita, M.: An efficient augmented context-free parsing algorithm. Computational Linguistics 13(1), 31\u201346 (1987)","journal-title":"Computational Linguistics"},{"key":"9683_CR29","doi-asserted-by":"crossref","unstructured":"Yoshinaka, R.: Learning conjunctive grammars and contextual binary feature grammars. Language and Automata Theory and Applications (LATA 2015, Nice, France, 2\u20136, March 2015), LNCS 8977, 623\u2013635","DOI":"10.1007\/978-3-319-15579-1_49"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9683-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9683-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9683-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9683-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T04:25:52Z","timestamp":1568003152000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9683-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,6]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["9683"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9683-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,6]]}}}