{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T18:29:02Z","timestamp":1778783342262,"version":"3.51.4"},"publisher-location":"Cham","reference-count":74,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319986531","type":"print"},{"value":"9783319986548","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98654-8_4","type":"book-chapter","created":{"date-parts":[[2018,8,4]],"date-time":"2018-08-04T19:43:57Z","timestamp":1533411837000},"page":"36-59","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A Tale of Conjunctive Grammars"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1615-2725","authenticated-orcid":false,"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,5]]},"reference":[{"issue":"3","key":"4_CR1","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-540-69937-8_6","volume":"50","author":"T Aizikowitz","year":"2013","unstructured":"Aizikowitz, T., Kaminski, M.: Conjunctive grammars and alternating pushdown automata. Acta Informatica 50(3), 175\u2013197 (2013). \n                    https:\/\/doi.org\/10.1007\/978-3-540-69937-8_6","journal-title":"Acta Informatica"},{"issue":"6","key":"4_CR2","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1142\/S0129054114500336","volume":"25","author":"T Aizikowitz","year":"2014","unstructured":"Aizikowitz, T., Kaminski, M.: Linear conjunctive grammars and one-turn synchronized alternating pushdown automata. Int. J. Found. Comput. Sci. 25(6), 781\u2013802 (2014). \n                    https:\/\/doi.org\/10.1142\/S0129054114500336","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"8","key":"4_CR3","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1016\/j.jcss.2016.05.008","volume":"82","author":"T Aizikowitz","year":"2016","unstructured":"Aizikowitz, T., Kaminski, M.: LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata. J. Comput. Syst. Sci. 82(8), 1329\u20131359 (2016). \n                    https:\/\/doi.org\/10.1016\/j.jcss.2016.05.008","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR4","unstructured":"Ajdukiewicz, K.: Die syntaktische Konnexit\u00e4t. In: Ajdukiewicz, K., Ingarden, R., Twardowski, K. (eds.) Studia Philosophica, vol. 1, pp. 1\u201327 (1935)"},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-642-59136-5_3","volume-title":"Handbook of Formal Languages","author":"J Autebert","year":"1997","unstructured":"Autebert, J., Berstel, J., Boasson, L.: Context-free languages and pushdown automata. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1, pp. 111\u2013174. Springer, Heidelberg (1997). \n                    https:\/\/doi.org\/10.1007\/978-3-642-59136-5_3"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-319-77313-1_5","volume-title":"Language and Automata Theory and Applications","author":"E Bakinova","year":"2018","unstructured":"Bakinova, E., Basharin, A., Batmanov, I., Lyubort, K., Okhotin, A., Sazhneva, E.: Formal languages over GF(2). In: Klein, S.T., Mart\u00edn-Vide, C., Shapira, D. (eds.) LATA 2018. LNCS, vol. 10792, pp. 68\u201379. Springer, Cham (2018). \n                    https:\/\/doi.org\/10.1007\/978-3-319-77313-1_5"},{"key":"4_CR7","first-page":"155","volume":"9F","author":"Y Bar-Hillel","year":"1960","unstructured":"Bar-Hillel, Y., Gaifman, H., Shamir, E.: On categorial and phrase structure grammars. Bull. Res. Counc. Isr. 9F, 155\u2013166 (1960)","journal-title":"Bull. Res. Counc. Isr."},{"key":"4_CR8","unstructured":"Barash, M.: Programming language specification by a grammar with contexts. In: NCMA (2013)"},{"key":"4_CR9","doi-asserted-by":"publisher","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). \n                    https:\/\/doi.org\/10.1016\/j.ic.2014.03.003","journal-title":"Inf. Comput."},{"key":"4_CR10","doi-asserted-by":"publisher","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). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2015.05.004","journal-title":"Theor. Comput. Sci."},{"key":"4_CR11","doi-asserted-by":"crossref","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). \n                    http:\/\/dx.doi.org\/10.1051\/ita\/2015004","DOI":"10.1051\/ita\/2015004"},{"issue":"2","key":"4_CR12","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/s00224-016-9683-3","volume":"61","author":"M Barash","year":"2017","unstructured":"Barash, M., Okhotin, A.: Generalized LR parsing algorithm for grammars with one-sided contexts. Theory Comput. Syst. 61(2), 581\u2013605 (2017). \n                    https:\/\/doi.org\/10.1007\/s00224-016-9683-3","journal-title":"Theory Comput. Syst."},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.tcs.2017.11.006","volume":"719","author":"M Barash","year":"2018","unstructured":"Barash, M., Okhotin, A.: Linear-space recognition for grammars with contexts. Theor. Comput. Sci. 719, 73\u201385 (2018). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2017.11.006","journal-title":"Theor. Comput. Sci."},{"issue":"2\u20133","key":"4_CR14","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1023\/A:1009907814595","volume":"3","author":"P Boullier","year":"2000","unstructured":"Boullier, P.: A cubic time extension of context-free grammars. Grammars 3(2\u20133), 111\u2013131 (2000). \n                    https:\/\/doi.org\/10.1023\/A:1009907814595","journal-title":"Grammars"},{"issue":"3","key":"4_CR15","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1109\/TIT.1956.1056813","volume":"2","author":"N Chomsky","year":"1956","unstructured":"Chomsky, N.: Three models for the description of language. IRE Trans. Inf. Theory 2(3), 113\u2013124 (1956). \n                    https:\/\/doi.org\/10.1109\/TIT.1956.1056813","journal-title":"IRE Trans. Inf. Theory"},{"key":"4_CR16","unstructured":"Clark, A., Eyraud, R., Habrard, A.: Using contextual representations to efficiently learn context-free languages. J. Mach. Learn. Res. 11, 2707\u20132744 (2010). \n                    http:\/\/www.jmlr.org\/papers\/v11\/clark10a.html"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/321127.321132","volume":"9","author":"S Ginsburg","year":"1962","unstructured":"Ginsburg, S., Rice, H.G.: Two families of languages related to ALGOL. J. ACM 9, 350\u2013371 (1962). \n                    https:\/\/doi.org\/10.1145\/321127.321132","journal-title":"J. ACM"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/321250.321254","volume":"12","author":"SA Greibach","year":"1965","unstructured":"Greibach, S.A.: A new normal-form theorem for context-free phrase structure grammars. J. ACM 12, 42\u201352 (1965). \n                    https:\/\/doi.org\/10.1145\/321250.321254","journal-title":"J. ACM"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/B978-0-12-708240-0.50008-3","volume-title":"Theoretical Studies in Computer Science","author":"SA Greibach","year":"1992","unstructured":"Greibach, S.A., Shi, W., Simonson, S.: Single tree grammars. In: Ullman, J.D. (ed.) Theoretical Studies in Computer Science, pp. 73\u201399. Academic Press, Cambridge (1992)"},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(91)90205-G","volume":"80","author":"S Heilbrunner","year":"1991","unstructured":"Heilbrunner, S., Schmitz, L.: An efficient recognizer for the Boolean closure of context-free languages. Theor. Comput. Sci. 80, 53\u201375 (1991). \n                    https:\/\/doi.org\/10.1016\/0304-3975(91)90205-G","journal-title":"Theor. Comput. Sci."},{"key":"4_CR21","unstructured":"Hellings, J.: Conjunctive context-free path queries. In: 17th International Conference on Database Theory, ICDT 2014, Athens, Greece, 24\u201328 March 2014, pp. 119\u2013130 (2014)"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0304-3975(84)90015-X","volume":"29","author":"OH Ibarra","year":"1984","unstructured":"Ibarra, O.H., Kim, S.M.: Characterizations and computational complexity of systolic trellis automata. Theor. Comput. Sci. 29, 123\u2013153 (1984). \n                    https:\/\/doi.org\/10.1016\/0304-3975(84)90015-X","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"4_CR23","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1142\/S012905410800584X","volume":"19","author":"A Je\u017c","year":"2008","unstructured":"Je\u017c, A.: Conjunctive grammars can generate non-regular unary languages. Int. J. Found. Comput. Sci. 19(3), 597\u2013615 (2008). \n                    https:\/\/doi.org\/10.1142\/S012905410800584X","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"4_CR24","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s00224-008-9139-5","volume":"46","author":"A Je\u017c","year":"2010","unstructured":"Je\u017c, A., Okhotin, A.: Conjunctive grammars over a unary alphabet: undecidability and unbounded growth. Theory Comput. Syst. 46(1), 27\u201358 (2010). \n                    https:\/\/doi.org\/10.1007\/s00224-008-9139-5","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"4_CR25","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s00224-009-9246-y","volume":"48","author":"A Je\u017c","year":"2011","unstructured":"Je\u017c, A., Okhotin, A.: Complexity of equations over sets of natural numbers. Theory Comput. Syst. 48(2), 319\u2013342 (2011). \n                    https:\/\/doi.org\/10.1007\/s00224-009-9246-y","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"4_CR26","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s00224-011-9319-6","volume":"49","author":"A Je\u017c","year":"2011","unstructured":"Je\u017c, A., Okhotin, A.: One-nonterminal conjunctive grammars over a unary alphabet. Theory Comput. Syst. 49(2), 319\u2013342 (2011). \n                    https:\/\/doi.org\/10.1007\/s00224-011-9319-6","journal-title":"Theory Comput. Syst."},{"key":"4_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-642-31623-4_14","volume-title":"Descriptional Complexity of Formal Systems","author":"A Je\u017c","year":"2012","unstructured":"Je\u017c, A., Okhotin, A.: On the number of nonterminal symbols in unambiguous conjunctive grammars. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol. 7386, pp. 183\u2013195. Springer, Heidelberg (2012). \n                    https:\/\/doi.org\/10.1007\/978-3-642-31623-4_14"},{"key":"4_CR28","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.ic.2014.05.001","volume":"237","author":"A Je\u017c","year":"2014","unstructured":"Je\u017c, A., Okhotin, A.: Computational completeness of equations over sets of natural numbers. Inf. Comput. 237, 56\u201394 (2014). \n                    https:\/\/doi.org\/10.1016\/j.ic.2014.05.001","journal-title":"Inf. Comput."},{"key":"4_CR29","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2016.12.009","volume":"665","author":"A Je\u017c","year":"2017","unstructured":"Je\u017c, A., Okhotin, A.: Unambiguous conjunctive grammars over a one-symbol alphabet. Theor. Comput. Sci. 665, 13\u201339 (2017). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2016.12.009","journal-title":"Theor. Comput. Sci."},{"key":"4_CR30","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF00171695","volume":"1","author":"M Kanazawa","year":"1992","unstructured":"Kanazawa, M.: The Lambek calculus enriched with additional connectives. J. Log. Lang. Inf. 1, 141\u2013171 (1992). \n                    https:\/\/doi.org\/10.1007\/BF00171695","journal-title":"J. Log. Lang. Inf."},{"key":"4_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-319-64419-6_16","volume-title":"Theoretical Computer Science and Discrete Mathematics","author":"K Kanchan Devi","year":"2017","unstructured":"Kanchan Devi, K., Arumugam, S.: Probabilistic conjunctive grammar. In: Arumugam, S., Bagga, J., Beineke, L.W., Panda, B.S. (eds.) ICTCSDM 2016. LNCS, vol. 10398, pp. 119\u2013127. Springer, Cham (2017). \n                    https:\/\/doi.org\/10.1007\/978-3-319-64419-6_16"},{"issue":"6","key":"4_CR32","doi-asserted-by":"publisher","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(6), 607\u2013639 (1965). \n                    https:\/\/doi.org\/10.1016\/S0019-9958(65)90426-2","journal-title":"Inf. Control"},{"issue":"9","key":"4_CR33","doi-asserted-by":"publisher","first-page":"945","DOI":"10.1016\/j.ic.2009.05.002","volume":"207","author":"V Kountouriotis","year":"2009","unstructured":"Kountouriotis, V., Nomikos, C., Rondogiannis, P.: Well-founded semantics for Boolean grammars. Inf. Comput. 207(9), 945\u2013967 (2009). \n                    https:\/\/doi.org\/10.1016\/j.ic.2009.05.002","journal-title":"Inf. Comput."},{"key":"4_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-642-39998-5_15","volume-title":"Formal Grammar","author":"S Kuznetsov","year":"2013","unstructured":"Kuznetsov, S.: Conjunctive grammars in greibach normal form and the lambek calculus with additive connectives. In: Morrill, G., Nederhof, M.-J. (eds.) FG 2012-2013. LNCS, vol. 8036, pp. 242\u2013249. Springer, Heidelberg (2013). \n                    https:\/\/doi.org\/10.1007\/978-3-642-39998-5_15"},{"key":"4_CR35","doi-asserted-by":"crossref","unstructured":"Kuznetsov, S., Okhotin, A.: Conjunctive categorial grammars. In: Proceedings of the 15th Meeting on the Mathematics of Language, MOL 2017, London, UK, 13\u201314 July 2017, pp. 141\u2013151. ACL (2017)","DOI":"10.18653\/v1\/W17-3414"},{"key":"4_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/3-540-06841-4_65","volume-title":"Automata, Languages and Programming","author":"B Lang","year":"1974","unstructured":"Lang, B.: Deterministic techniques for efficient non-deterministic parsers. In: Loeckx, J. (ed.) ICALP 1974. LNCS, vol. 14, pp. 255\u2013269. Springer, Heidelberg (1974). \n                    https:\/\/doi.org\/10.1007\/3-540-06841-4_65"},{"issue":"2","key":"4_CR37","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/S1571-0661(05)80365-2","volume":"68","author":"M Lange","year":"2002","unstructured":"Lange, M.: Alternating context-free languages and linear time \n                    \n                      \n                    \n                    $$\\mu $$\n                  -calculus with sequential composition. Electron. Notes Theor. Comput. Sci. 68(2), 70\u201386 (2002). \n                    https:\/\/doi.org\/10.1016\/S1571-0661(05)80365-2","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"4_CR38","unstructured":"Latta, M., Wall, R.: Intersective context-free languages. In: Martin-Vide, C. (ed.) 9th Congress on Natural and Formal Languages, Reus, Spain, 20\u201322 December 1993, pp. 15\u201343 (1993)"},{"issue":"5","key":"4_CR39","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1142\/S0129054110007568","volume":"21","author":"T Lehtinen","year":"2010","unstructured":"Lehtinen, T., Okhotin, A.: Boolean grammars and GSM mappings. Int. J. Found. Comput. Sci. 21(5), 799\u2013815 (2010). \n                    https:\/\/doi.org\/10.1142\/S0129054110007568","journal-title":"Int. J. Found. Comput. Sci."},{"key":"4_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/978-3-642-14455-4_27","volume-title":"Developments in Language Theory","author":"T Lehtinen","year":"2010","unstructured":"Lehtinen, T., Okhotin, A.: On language equations \n                    \n                      \n                    \n                    $$XXK = XXL$$\n                   and \n                    \n                      \n                    \n                    $$XM = N$$\n                   over a unary alphabet. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol. 6224, pp. 291\u2013302. Springer, Heidelberg (2010). \n                    https:\/\/doi.org\/10.1007\/978-3-642-14455-4_27"},{"issue":"4","key":"4_CR41","first-page":"519","volume":"6","author":"A Okhotin","year":"2001","unstructured":"Okhotin, A.: Conjunctive grammars. J. Autom. Lang. Comb. 6(4), 519\u2013535 (2001)","journal-title":"J. Autom. Lang. Comb."},{"issue":"5","key":"4_CR42","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1023\/A:1020213411126","volume":"28","author":"A Okhotin","year":"2002","unstructured":"Okhotin, A.: Conjunctive grammars and systems of language equations. Program. Comput. Soft. 28(5), 243\u2013249 (2002). \n                    https:\/\/doi.org\/10.1023\/A:1020213411126","journal-title":"Program. Comput. Soft."},{"issue":"1","key":"4_CR43","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1023\/A:1014219530875","volume":"5","author":"A Okhotin","year":"2002","unstructured":"Okhotin, A.: Top-down parsing of conjunctive languages. Grammars 5(1), 21\u201340 (2002). \n                    https:\/\/doi.org\/10.1023\/A:1014219530875","journal-title":"Grammars"},{"issue":"2","key":"4_CR44","doi-asserted-by":"publisher","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(2), 81\u2013124 (2002). \n                    https:\/\/doi.org\/10.1023\/A:1016329527130","journal-title":"Grammars"},{"issue":"1","key":"4_CR45","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.ic.2004.03.006","volume":"194","author":"A Okhotin","year":"2004","unstructured":"Okhotin, A.: Boolean grammars. Inf. Comput. 194(1), 19\u201348 (2004). \n                    https:\/\/doi.org\/10.1016\/j.ic.2004.03.006","journal-title":"Inf. Comput."},{"issue":"1","key":"4_CR46","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1051\/ita:2004004","volume":"38","author":"A Okhotin","year":"2004","unstructured":"Okhotin, A.: On the equivalence of linear conjunctive grammars to trellis automata. Informatique Th\u00e9orique et Applications 38(1), 69\u201388 (2004). \n                    https:\/\/doi.org\/10.1051\/ita:2004004","journal-title":"Informatique Th\u00e9orique et Applications"},{"issue":"2\u20133","key":"4_CR47","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.tcs.2004.03.002","volume":"320","author":"A Okhotin","year":"2004","unstructured":"Okhotin, A.: On the number of nonterminals in linear conjunctive grammars. Theor. Comput. Sci. 320(2\u20133), 419\u2013448 (2004). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2004.03.002","journal-title":"Theor. Comput. Sci."},{"issue":"2\u20133","key":"4_CR48","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/j.tcs.2005.07.019","volume":"345","author":"A Okhotin","year":"2005","unstructured":"Okhotin, A.: The dual of concatenation. Theor. Comput. Sci. 345(2\u20133), 425\u2013447 (2005). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2005.07.019","journal-title":"Theor. Comput. Sci."},{"key":"4_CR49","unstructured":"Okhotin, A.: On the existence of a Boolean grammar for a simple programming language. In: Automata and Formal Languages, Proceedings of AFL 2005, Dobog\u00f3k\u0151, Hungary, 17\u201320 May 2005"},{"issue":"3","key":"4_CR50","doi-asserted-by":"publisher","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). \n                    https:\/\/doi.org\/10.1142\/S0129054106004029","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3\u20134","key":"4_CR51","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s00236-007-0045-0","volume":"44","author":"A Okhotin","year":"2007","unstructured":"Okhotin, A.: Recursive descent parsing for Boolean grammars. Acta Informatica 44(3\u20134), 167\u2013189 (2007). \n                    https:\/\/doi.org\/10.1007\/s00236-007-0045-0","journal-title":"Acta Informatica"},{"issue":"6","key":"4_CR52","doi-asserted-by":"publisher","first-page":"1361","DOI":"10.1142\/S0129054107005406","volume":"18","author":"A Okhotin","year":"2007","unstructured":"Okhotin, A.: Notes on dual concatenation. Int. J. Found. Comput. Sci. 18(6), 1361\u20131370 (2007). \n                    https:\/\/doi.org\/10.1142\/S0129054107005406","journal-title":"Int. J. Found. Comput. Sci."},{"key":"4_CR53","doi-asserted-by":"publisher","first-page":"1234","DOI":"10.1016\/j.ic.2008.03.023","volume":"206","author":"A Okhotin","year":"2008","unstructured":"Okhotin, A.: Unambiguous Boolean grammars. Inf. Comput. 206, 1234\u20131247 (2008). \n                    https:\/\/doi.org\/10.1016\/j.ic.2008.03.023","journal-title":"Inf. Comput."},{"issue":"39","key":"4_CR54","doi-asserted-by":"publisher","first-page":"5132","DOI":"10.1016\/j.tcs.2011.05.013","volume":"412","author":"A Okhotin","year":"2011","unstructured":"Okhotin, A.: Expressive power of LL(\n                    \n                      \n                    \n                    $$k$$\n                  ) Boolean grammars. Theor. Comput. Sci. 412(39), 5132\u20135155 (2011). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2011.05.013","journal-title":"Theor. Comput. Sci."},{"key":"4_CR55","doi-asserted-by":"publisher","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. Comput. Sci. Rev. 9, 27\u201359 (2013). \n                    https:\/\/doi.org\/10.1016\/j.cosrev.2013.06.001","journal-title":"Comput. Sci. Rev."},{"key":"4_CR56","doi-asserted-by":"publisher","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). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2013.09.011","journal-title":"Theor. Comput. Sci."},{"key":"4_CR57","doi-asserted-by":"publisher","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). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2015.03.041","journal-title":"Theor. Comput. Sci."},{"key":"4_CR58","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-319-34171-2_24","volume-title":"Computer Science \u2013 Theory and Applications","author":"A Okhotin","year":"2016","unstructured":"Okhotin, A.: The hardest language for conjunctive grammars. In: Kulikov, A.S., Woeginger, G.J. (eds.) CSR 2016. LNCS, vol. 9691, pp. 340\u2013351. Springer, Cham (2016). \n                    https:\/\/doi.org\/10.1007\/978-3-319-34171-2_24"},{"key":"4_CR59","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/978-3-319-77313-1_3","volume-title":"Language and Automata Theory and Applications","author":"A Okhotin","year":"2018","unstructured":"Okhotin, A.: Underlying principles and recurring ideas of formal grammars. In: Klein, S.T., Mart\u00edn-Vide, C., Shapira, D. (eds.) LATA 2018. LNCS, vol. 10792, pp. 36\u201359. Springer, Cham (2018). \n                    https:\/\/doi.org\/10.1007\/978-3-319-77313-1_3"},{"issue":"26\u201328","key":"4_CR60","doi-asserted-by":"publisher","first-page":"2559","DOI":"10.1016\/j.tcs.2010.03.015","volume":"411","author":"A Okhotin","year":"2010","unstructured":"Okhotin, A., Reitwie\u00dfner, C.: Conjunctive grammars with restricted disjunction. Theor. Comput. Sci. 411(26\u201328), 2559\u20132571 (2010). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2010.03.015","journal-title":"Theor. Comput. Sci."},{"key":"4_CR61","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.tcs.2012.06.032","volume":"457","author":"A Okhotin","year":"2012","unstructured":"Okhotin, A., Reitwie\u00dfner, C.: Parsing Boolean grammars over a one-letter alphabet using online convolution. Theor. Comput. Sci. 457, 149\u2013157 (2012). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2012.06.032","journal-title":"Theor. Comput. Sci."},{"key":"4_CR62","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2012.01.004","volume":"212","author":"A Okhotin","year":"2012","unstructured":"Okhotin, A., Rondogiannis, P.: On the expressive power of univariate equations over sets of natural numbers. Inf. Comput. 212, 1\u201314 (2012). \n                    https:\/\/doi.org\/10.1016\/j.ic.2012.01.004","journal-title":"Inf. Comput."},{"key":"4_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/978-3-319-06686-8_24","volume-title":"Computer Science - Theory and Applications","author":"M Rabkin","year":"2014","unstructured":"Rabkin, M.: Recognizing two-sided contexts in cubic time. In: Hirsch, E.A., Kuznetsov, S.O., Pin, J.\u00c9., Vereshchagin, N.K. (eds.) CSR 2014. LNCS, vol. 8476, pp. 314\u2013324. Springer, Cham (2014). \n                    https:\/\/doi.org\/10.1007\/978-3-319-06686-8_24"},{"key":"4_CR64","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1016\/S0019-9958(70)90446-8","volume":"17","author":"DJ Rosenkrantz","year":"1970","unstructured":"Rosenkrantz, D.J., Stearns, R.E.: Properties of deterministic top-down grammars. Inf. Control 17, 226\u2013256 (1970). \n                    https:\/\/doi.org\/10.1016\/S0019-9958(70)90446-8","journal-title":"Inf. Control"},{"issue":"4","key":"4_CR65","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. Comput. Linguist. 14(4), 1\u20139 (1988)","journal-title":"Comput. Linguist."},{"key":"4_CR66","unstructured":"Szabari, A.: Alternuj\u00face Z\u00e1sobn\u00edkov\u00e9 Automaty (Alternating Pushdown Automata), in Slovak, diploma work (M.Sc. thesis), University of Ko\u0161ice (Czechoslovakia), 45 pp. (1991)"},{"issue":"1\u20132","key":"4_CR67","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/0304-3975(94)00212-2","volume":"141","author":"V Terrier","year":"1995","unstructured":"Terrier, V.: On real-time one-way cellular array. Theor. Comput. Sci. 141(1\u20132), 331\u2013335 (1995). \n                    https:\/\/doi.org\/10.1016\/0304-3975(94)00212-2","journal-title":"Theor. Comput. Sci."},{"key":"4_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-319-58631-1_14","volume-title":"Cellular Automata and Discrete Complex Systems","author":"V Terrier","year":"2017","unstructured":"Terrier, V.: Some computational limits of trellis automata. In: Dennunzio, A., Formenti, E., Manzoni, L., Porreca, A.E. (eds.) AUTOMATA 2017. LNCS, vol. 10248, pp. 176\u2013186. Springer, Cham (2017). \n                    https:\/\/doi.org\/10.1007\/978-3-319-58631-1_14"},{"issue":"1","key":"4_CR69","first-page":"31","volume":"13","author":"M Tomita","year":"1987","unstructured":"Tomita, M.: An efficient augmented context-free parsing algorithm. Comput. Linguist. 13(1), 31\u201346 (1987)","journal-title":"Comput. Linguist."},{"issue":"2","key":"4_CR70","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\u2013314 (1975). \n                    https:\/\/doi.org\/10.1016\/S0022-0000(75)80046-8","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR71","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/978-3-662-41148-3_11","volume-title":"GI Gesellschaft f\u00fcr Informatik e. V.","author":"D Wotschke","year":"1973","unstructured":"Wotschke, D.: The Boolean closures of the deterministic and nondeterministic context-free languages. In: Brauer, W. (ed.) GI Gesellschaft f\u00fcr Informatik e. V. LNCS, vol. 1, pp. 113\u2013121. Springer, Heidelberg (1973). \n                    https:\/\/doi.org\/10.1007\/978-3-662-41148-3_11"},{"key":"4_CR72","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/978-3-319-15579-1_49","volume-title":"Language and Automata Theory and Applications","author":"R Yoshinaka","year":"2015","unstructured":"Yoshinaka, R.: Learning conjunctive grammars and contextual binary feature grammars. In: Dediu, A.-H., Formenti, E., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2015. LNCS, vol. 8977, pp. 623\u2013635. Springer, Cham (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-319-15579-1_49"},{"key":"4_CR73","doi-asserted-by":"crossref","unstructured":"Zhang, Q., Su, Z.: Context-sensitive data-dependence analysis via linear conjunctive language reachability. In: Principles of Programming Languages (POPL 2017), pp. 344\u2013358 (2017). \n                    http:\/\/dx.doi.org\/10.1145\/3009837.3009848","DOI":"10.1145\/3009837.3009848"},{"key":"4_CR74","unstructured":"Zier-Vogel, R., Domaratzki, M.: RNA pseudoknot prediction through stochastic conjunctive grammars. In: The Nature of Computation: Logic, Algorithms, Applications (CiE 2013, Milan, Italy, 1\u20135 July 2013), Informal Proceedings, pp. 80\u201389 (2013)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98654-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,9,2]],"date-time":"2018-09-02T19:07:41Z","timestamp":1535915261000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-98654-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319986531","9783319986548"],"references-count":74,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98654-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]}}}