{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T04:44:45Z","timestamp":1725857085489},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319341705"},{"type":"electronic","value":"9783319341712"}],"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-34171-2_24","type":"book-chapter","created":{"date-parts":[[2016,5,30]],"date-time":"2016-05-30T02:34:18Z","timestamp":1464575658000},"page":"340-351","source":"Crossref","is-referenced-by-count":2,"title":["The Hardest Language for Conjunctive Grammars"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,31]]},"reference":[{"key":"24_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/978-3-642-20712-9_27","volume-title":"Computer Science \u2013 Theory and Applications","author":"T Aizikowitz","year":"2011","unstructured":"Aizikowitz, T., Kaminski, M.: LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol. 6651, pp. 345\u2013358. Springer, Heidelberg (2011)"},{"issue":"1","key":"24_CR2","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF01768474","volume":"11","author":"J-M Autebert","year":"1977","unstructured":"Autebert, J.-M.: Non-principalit\u00e9 du cylindre des langages \u00e0 compteur. Math. Syst. Theory 11(1), 157\u2013167 (1977)","journal-title":"Math. Syst. Theory"},{"key":"24_CR3","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":"24_CR4","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. Theoret. Comput. Sci. 591, 134\u2013153 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR5","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/BF01768473","volume":"11","author":"L Boasson","year":"1977","unstructured":"Boasson, L., Nivat, M.: Le cylindre des langages lin\u00e9aires. Math. Syst. Theory 11, 147\u2013155 (1977)","journal-title":"Math. Syst. Theory"},{"issue":"3","key":"24_CR6","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1051\/ita\/1979130302411","volume":"13","author":"K \u010cul\u00edk II","year":"1979","unstructured":"\u010cul\u00edk II, K., Maurer, H.A.: On simple representations of language families. RAIRO Informatique Th\u00e9orique et Appl. 13(3), 241\u2013250 (1979)","journal-title":"RAIRO Informatique Th\u00e9orique et Appl."},{"key":"24_CR7","doi-asserted-by":"crossref","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)","journal-title":"J. ACM"},{"issue":"4","key":"24_CR8","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"SA Greibach","year":"1973","unstructured":"Greibach, S.A.: The hardest context-free language. SIAM J. Comput. 2(4), 304\u2013310 (1973)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"24_CR9","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0203009","volume":"3","author":"SA Greibach","year":"1974","unstructured":"Greibach, S.A.: Jump PDA\u2019s and hierarchies of deterministic context-free languages. SIAM J. Comput. 3(2), 111\u2013127 (1974)","journal-title":"SIAM J. Comput."},{"issue":"9","key":"24_CR10","doi-asserted-by":"crossref","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)","journal-title":"Inf. Comput."},{"issue":"5","key":"24_CR11","doi-asserted-by":"crossref","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)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"24_CR12","first-page":"519","volume":"6","author":"A Okhotin","year":"2001","unstructured":"Okhotin, A.: Conjunctive grammars. J. Automata Lang. Comb. 6(4), 519\u2013535 (2001)","journal-title":"J. Automata Lang. Comb."},{"issue":"5","key":"24_CR13","doi-asserted-by":"crossref","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. Sci. 28(5), 243\u2013249 (2002)","journal-title":"Program. Comput. Sci."},{"issue":"1","key":"24_CR14","doi-asserted-by":"crossref","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)","journal-title":"Inf. Comput."},{"issue":"2\u20133","key":"24_CR15","doi-asserted-by":"crossref","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. Theoret. Comput. Sci. 345(2\u20133), 425\u2013447 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR16","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. Comput. Sci. Rev. 9, 27\u201359 (2013)","journal-title":"Comput. Sci. Rev."},{"key":"24_CR17","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. Theoret. Comput. Sci. 516, 101\u2013120 (2014)","journal-title":"Theoret. Comput. Sci."},{"issue":"26\u201328","key":"24_CR18","doi-asserted-by":"crossref","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. Theoret. Comput. Sci. 411(26\u201328), 2559\u20132571 (2010)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"24_CR19","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0304-3975(91)90374-B","volume":"88","author":"H Seki","year":"1991","unstructured":"Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. Theoret. Comput. Sci. 88(2), 191\u2013229 (1991)","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR20","doi-asserted-by":"crossref","unstructured":"Vijay-Shanker, K., Weir, D.J., Joshi, A.K.: Characterizing structural descriptions produced by various grammatical formalisms. In: 25th Annual Meeting of the Association for Computational Linguistics (ACL 1987), pp. 104\u2013111 (1987)","DOI":"10.3115\/981175.981190"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-34171-2_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T11:19:49Z","timestamp":1498303189000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-34171-2_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319341705","9783319341712"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-34171-2_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}