{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T19:45:22Z","timestamp":1769975122450,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,12,23]],"date-time":"2009-12-23T00:00:00Z","timestamp":1261526400000},"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,2]]},"DOI":"10.1007\/s00224-009-9246-y","type":"journal-article","created":{"date-parts":[[2009,12,22]],"date-time":"2009-12-22T15:24:46Z","timestamp":1261495486000},"page":"319-342","source":"Crossref","is-referenced-by-count":18,"title":["Complexity of Equations over Sets of Natural Numbers"],"prefix":"10.1007","volume":"48","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,12,23]]},"reference":[{"issue":"7","key":"9246_CR1","first-page":"7.1","volume":"6","author":"R.P. Brent","year":"1984","unstructured":"Brent, R.P., Goldschlager, L.M.: A parallel algorithm for context-free parsing. Aust. Comput. Sci. Commun. 6(7), 7.1\u20137.10 (1984)","journal-title":"Aust. Comput. Sci. Commun."},{"key":"9246_CR2","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-3-540-74240-1_12","volume-title":"Fundamentals of Computation Theory","author":"H.-G. Breunig","year":"2007","unstructured":"Breunig, H.-G.: The complexity of membership problems for circuits over sets of positive numbers. In: Fundamentals of Computation Theory, FCT 2007, Budapest, Hungary, August 27\u201330, 2007. LNCS, vol.\u00a04639, pp.\u00a0125\u2013136. Springer, Berlin (2007)"},{"issue":"2","key":"9246_CR3","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jcss.1998.1615","volume":"58","author":"J.-Y. Cai","year":"1999","unstructured":"Cai, J.-Y., Sivakumar, D.: Sparse hard sets for P: resolution of a conjecture of Hartmanis. J.\u00a0Comput. Syst. Sci. 58(2), 280\u2013296 (1999)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"1","key":"9246_CR4","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM 28(1), 114\u2013133 (1981)","journal-title":"J. ACM"},{"key":"9246_CR5","doi-asserted-by":"crossref","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)","journal-title":"J. ACM"},{"key":"9246_CR6","series-title":"LNCS","first-page":"127","volume-title":"Computer Science in Russia","author":"C. Gla\u00dfer","year":"2007","unstructured":"Gla\u00dfer, C., Herr, K., Reitwie\u00dfner, C., Travers, S.D., Waldherr, M.: Equivalence problems for circuits over sets of natural numbers. In: Computer Science in Russia, CSR 2007, Ekaterinburg, Russia, September 3\u20137, 2007. LNCS, vol.\u00a04649, pp. 127\u2013138. Springer, Berlin (2007)."},{"issue":"1","key":"9246_CR7","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":"9246_CR8","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":"9246_CR9","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":"1","key":"9246_CR10","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N.D. Jones","year":"1976","unstructured":"Jones, N.D., Laaser, W.T.: Complete problems for deterministic polynomial time. Theor. Comput. Sci. 3(1), 105\u2013117 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9246_CR11","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/s00224-006-1321-z","volume":"40","author":"M. Kunc","year":"2007","unstructured":"Kunc, M.: The power of commuting with finite sets of words. Theory Comput. Syst. 40(4), 521\u2013551 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9246_CR12","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 we know about language equations? In: Developments in Language Theory, DLT 2007, Turku, Finland, July 3\u20136, 2007. LNCS, vol.\u00a04588, pp. 23\u201327. Springer, Berlin (2007)"},{"issue":"5","key":"9246_CR13","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."},{"issue":"1","key":"9246_CR14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.ipl.2004.01.002","volume":"90","author":"N. Markey","year":"2004","unstructured":"Markey, N., Schnoebelen, Ph.: A PTIME-complete matching problem for SLP-compressed words. Inf. Process. Lett. 90(1), 3\u20136 (2004)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9246_CR15","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.: The complexity of membership problems for circuits over sets of natural numbers. Comput. Complex. 16(3), 211\u2013244 (2007)","journal-title":"Comput. Complex."},{"key":"9246_CR16","unstructured":"Ogihara, M.: Sparse hard sets for P yield space-efficient algorithms. Chic. J. Theor. Comput. Sci. (1996), article\u00a02"},{"issue":"4","key":"9246_CR17","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":"9246_CR18","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":"5","key":"9246_CR19","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/S0020-0190(02)00511-2","volume":"86","author":"A. Okhotin","year":"2003","unstructured":"Okhotin, A.: The hardest linear conjunctive language. Inf. Process. Lett. 86(5), 247\u2013253 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9246_CR20","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/j.tcs.2005.07.038","volume":"349","author":"A. Okhotin","year":"2005","unstructured":"Okhotin, A.: Unresolved systems of language equations: expressive power and decision problems. Theor. Comput. Sci. 349(3), 283\u2013308 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9246_CR21","doi-asserted-by":"crossref","unstructured":"Okhotin, A.: Decision problems for language equations. J. Comput. Syst. Sci. 76 (2010), to appear","DOI":"10.1016\/j.jcss.2009.08.002"},{"key":"9246_CR22","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":"9246_CR23","series-title":"LNCS","first-page":"315","volume-title":"Fundamentals of Computation Theory","author":"W. Rytter","year":"1985","unstructured":"Rytter, W.: On the recognition of context-free languages. In: Fundamentals of Computation Theory, FCT 1985, Cottbus, Germany. LNCS, vol.\u00a0208, pp. 315\u2013322. Springer, Berlin (1985)"},{"key":"9246_CR24","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: 5th Annual ACM Symposium on Theory of Computing, STOC 1973, Austin, USA, April 30\u2013May 2, 1973, pp. 1\u20139 (1973)"},{"issue":"1\u20133","key":"9246_CR25","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.tcs.2006.08.017","volume":"369","author":"S.D. Travers","year":"2006","unstructured":"Travers, S.D.: The complexity of membership problems for circuits over sets of integers. Theor. Comput. Sci. 369(1\u20133), 211\u2013229 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9246_CR26","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1006\/jcss.2001.1768","volume":"63","author":"K. Yang","year":"2001","unstructured":"Yang, K.: Integer circuit evaluation is PSPACE-complete. J. Comput. Syst. Sci. 63(2), 288\u2013303 (2001)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9246-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9246-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9246-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T18:13:41Z","timestamp":1558721621000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9246-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,23]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["9246"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9246-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12,23]]}}}