{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:39Z","timestamp":1759637919308},"reference-count":15,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2003,4,1]],"date-time":"2003-04-01T00:00:00Z","timestamp":1049155200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3760,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,4]]},"DOI":"10.1016\/s0304-3975(02)00543-1","type":"journal-article","created":{"date-parts":[[2003,4,23]],"date-time":"2003-04-23T23:53:40Z","timestamp":1051142020000},"page":"663-685","source":"Crossref","is-referenced-by-count":14,"title":["On the closure properties of linear conjunctive languages"],"prefix":"10.1016","volume":"299","author":[{"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(02)00543-1_BIB1","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0019-9958(64)90294-3","article-title":"On a family of linear grammars","volume":"7","author":"Amar","year":"1964","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(02)00543-1_BIB2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0304-3975(80)90069-9","article-title":"On equations for regular languages, finite automata and sequential networks","volume":"10","author":"Brzozowski","year":"1980","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(02)00543-1_BIB3","series-title":"Computer Programming and Formal Systems","first-page":"118","article-title":"The algebraic theory of context-free languages","author":"Chomsky","year":"1963"},{"issue":"2","key":"10.1016\/S0304-3975(02)00543-1_BIB4","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0019-9958(63)90149-9","article-title":"The undecidability of the ambiguity problem for minimal linear grammars","volume":"6","author":"Greibach","year":"1963","journal-title":"Inform. and Control"},{"issue":"4","key":"10.1016\/S0304-3975(02)00543-1_BIB5","doi-asserted-by":"crossref","first-page":"582","DOI":"10.1145\/321356.321365","article-title":"The unsolvability of the recognition of linear context-free languages","volume":"13","author":"Greibach","year":"1966","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(02)00543-1_BIB6","doi-asserted-by":"crossref","unstructured":"M. Holzer, K.-J. Lange, On the complexities of linear LL(1) and LR(1) grammars, Proc. 9th Internat. Conf. on Fundamentals of Computation Theory, Lecture Notes in Computer Science, Vol. 710, Springer, Berlin, 1993, pp. 299\u2013308.","DOI":"10.1007\/3-540-57163-9_25"},{"key":"10.1016\/S0304-3975(02)00543-1_BIB7","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0020-0190(88)90047-6","article-title":"Some subclasses of context-free languages in NC1","volume":"29","author":"Ibarra","year":"1988","journal-title":"Inform. Process. Lett."},{"issue":"4","key":"10.1016\/S0304-3975(02)00543-1_BIB8","first-page":"519","article-title":"Conjunctive grammars","volume":"6","author":"Okhotin","year":"2001","journal-title":"J. Automata Languages Combin."},{"key":"10.1016\/S0304-3975(02)00543-1_BIB9","unstructured":"A. Okhotin, A recognition and parsing algorithm for arbitrary conjunctive grammars, Theoret. Comput. Sci., to appear. (Until they are actually published, the papers [9] and [10] are temporarily available at http:\/\/www.cs.queensu.ca\/home\/okhotin\/conjunctive\/)."},{"key":"10.1016\/S0304-3975(02)00543-1_BIB10","doi-asserted-by":"crossref","unstructured":"A. Okhotin, Conjunctive grammars and systems of language equations, Programming and Computer Software 28 (2002) 243\u2013249; translated from the Russian original in Programmirovanie 28 (2002).","DOI":"10.1023\/A:1020213411126"},{"key":"10.1016\/S0304-3975(02)00543-1_BIB11","unstructured":"G. P\u0103un, G. Rozenberg, A. Salomaa, On strongly context-free languages, Technical Report No. 205, Turku Centre for Computer Science, 1998."},{"key":"10.1016\/S0304-3975(02)00543-1_BIB12","first-page":"175","article-title":"A machine realization of the linear context-free languages","volume":"10","author":"Rosenberg","year":"1967","journal-title":"Inform. and Comput."},{"issue":"4","key":"10.1016\/S0304-3975(02)00543-1_BIB13","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/321906.321913","article-title":"A note on tape-bounded complexity classes and linear context-free languages","volume":"22","author":"Sudborough","year":"1975","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(02)00543-1_BIB14","unstructured":"Whale Calf, a parser generator for conjunctive grammars, available at http:\/\/www.cs.queensu.ca\/home\/okhotin\/whalecalf\/."},{"key":"10.1016\/S0304-3975(02)00543-1_BIB15","doi-asserted-by":"crossref","unstructured":"D. Wotschke, The Boolean Closures of Deterministic and Nondeterministic Context-free Languages, Lecture Notes in Computer Science, Vol. 1, Springer, Berlin, 1973, pp. 113\u2013121.","DOI":"10.1007\/978-3-662-41148-3_11"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397502005431?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397502005431?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,17]],"date-time":"2020-03-17T19:01:05Z","timestamp":1584471665000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397502005431"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":15,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2003,4]]}},"alternative-id":["S0304397502005431"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(02)00543-1","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}