{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:12:58Z","timestamp":1759637578369},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,3,10]],"date-time":"2011-03-10T00:00:00Z","timestamp":1299715200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2011,8]]},"DOI":"10.1007\/s00224-011-9319-6","type":"journal-article","created":{"date-parts":[[2011,3,9]],"date-time":"2011-03-09T09:46:19Z","timestamp":1299663979000},"page":"319-342","source":"Crossref","is-referenced-by-count":9,"title":["One-Nonterminal Conjunctive Grammars over a Unary Alphabet"],"prefix":"10.1007","volume":"49","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,3,10]]},"reference":[{"key":"9319_CR1","doi-asserted-by":"crossref","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, S. (ed.) Handbook of Formal Languages, vol. 1, pp. 111\u2013174. Springer, Berlin (1997)"},{"issue":"1","key":"9319_CR2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0019-9958(83)80022-9","volume":"57","author":"D.T. Huynh","year":"1983","unstructured":"Huynh, D.T.: Commutative grammars: the complexity of uniform word problems. Inf. Control 57(1), 21\u201339 (1983)","journal-title":"Inf. Control"},{"issue":"3","key":"9319_CR3","doi-asserted-by":"crossref","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)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"9319_CR4","doi-asserted-by":"crossref","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)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"9319_CR5","doi-asserted-by":"crossref","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)","journal-title":"Theory Comput. Syst."},{"key":"9319_CR6","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/978-3-540-70583-3_6","volume-title":"35th International Colloquium on Automata, Languages and Programming","author":"A. Je\u017c","year":"2008","unstructured":"Je\u017c, A., Okhotin, A.: On the computational completeness of equations over sets of natural numbers. In: 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Reykjavik, Iceland, July 7\u201311, 2008, pp. 63\u201374 (2008)"},{"key":"9319_CR7","first-page":"577","volume-title":"STACS 2009","author":"A. Je\u017c","year":"2009","unstructured":"Je\u017c, A., Okhotin, A.: Equations over sets of natural numbers with addition only. In: STACS 2009, Freiburg, Germany, 26\u201328 February 2009, pp. 577\u2013588 (2009)"},{"issue":"2","key":"9319_CR8","first-page":"121","volume":"15","author":"I. Kats\u00e1nyi","year":"2011","unstructured":"Kats\u00e1nyi, I.: Sets of integers in different number systems and the Chomsky hierarchy. Acta Cybern. 15(2), 121\u2013136 (2011)","journal-title":"Acta Cybern."},{"key":"9319_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/978-3-540-73208-2_3","volume-title":"Developments in Language Theory","author":"M. Kunc","year":"2007","unstructured":"Kunc, M.: What do\u00a0we know about language equations. In: Developments in Language Theory, DLT 2007, Turku, Finland, July 3\u20136 2007. LNCS, vol.\u00a04588, pp. 23\u201327 (2007)"},{"key":"9319_CR10","series-title":"LNCS","doi-asserted-by":"crossref","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 XXK=XXL and XM=N over a unary alphabet. In: Developments in Language Theory, DLT 2010, London, Ontario, Canada, August 17\u201320, 2010. LNCS, vol.\u00a06224, pp. 291\u2013302 (2010)"},{"issue":"5","key":"9319_CR11","doi-asserted-by":"crossref","first-page":"1210","DOI":"10.1137\/S0097539704445950","volume":"35","author":"M. Lohrey","year":"2006","unstructured":"Lohrey, M.: Word problems and membership problems on compressed words. SIAM J. Comput. 35(5), 1210\u20131240 (2006)","journal-title":"SIAM J. Comput."},{"key":"9319_CR12","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s00037-007-0229-6","volume":"16","author":"P. McKenzie","year":"2007","unstructured":"McKenzie, P., Wagner, K.W.: The complexity of membership problems for circuits over sets of natural numbers. Comput. Complex. 16, 211\u2013244 (2007)","journal-title":"Comput. Complex."},{"issue":"4","key":"9319_CR13","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."},{"key":"9319_CR14","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. Softw. 28, 243\u2013249 (2002)","journal-title":"Program. Comput. Softw."},{"key":"9319_CR15","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/S0304-3975(02)00853-8","volume":"302","author":"A. Okhotin","year":"2003","unstructured":"Okhotin, A.: A recognition and parsing algorithm for arbitrary conjunctive grammars. Theor. Comput. Sci. 302, 365\u2013399 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"2\u20133","key":"9319_CR16","doi-asserted-by":"crossref","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)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9319_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."},{"issue":"3\u20134","key":"9319_CR18","doi-asserted-by":"crossref","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 Inform. 44(3\u20134), 167\u2013189 (2007)","journal-title":"Acta Inform."},{"key":"9319_CR19","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1007\/978-3-642-14455-4_31","volume-title":"Developments in Language Theory","author":"A. Okhotin","year":"2010","unstructured":"Okhotin, A.: Fast parsing for Boolean grammars: a generalization of Valiant\u2019s algorithm. In: Developments in Language Theory, DLT 2010, London, Ontario, Canada, August 17\u201320, 2010. LNCS, vol.\u00a06224, pp. 340\u2013351 (2010)"},{"key":"9319_CR20","series-title":"IFIP","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/978-0-387-09680-3_15","volume-title":"IFIP Intl. Conf. on Theoretical Computer Science","author":"A. Okhotin","year":"2008","unstructured":"Okhotin, A., Rondogiannis, P.: On the expressive power of univariate equations over sets of natural numbers. In: IFIP Intl. Conf. on Theoretical Computer Science. TCS 2008, Milan, Italy, 8\u201310 September 2008. IFIP, vol. 273, pp. 215\u2013227 (2008)"},{"key":"9319_CR21","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/978-3-642-60207-8_23","volume-title":"Jewels Are Forever","author":"W. Plandowski","year":"1999","unstructured":"Plandowski, W., Rytter, W.: Complexity of language recognition problems for compressed words. In: Karhum\u00e4ki, J., Maurer, H.A., P\u0103un, G., Rozenberg, G. (eds.) Jewels Are Forever, pp. 262\u2013272. Springer, Berlin (1999)"},{"key":"9319_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/800125.804029","volume-title":"STOC 1973","author":"L.J. Stockmeyer","year":"1973","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: STOC 1973, pp. 1\u20139 (1973)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9319-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9319-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9319-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:22Z","timestamp":1558698862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9319-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,10]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["9319"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9319-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,10]]}}}