{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T05:25:35Z","timestamp":1772861135671,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,8]]},"DOI":"10.1007\/s00224-011-9352-5","type":"journal-article","created":{"date-parts":[[2011,8,3]],"date-time":"2011-08-03T16:47:47Z","timestamp":1312390067000},"page":"196-228","source":"Crossref","is-referenced-by-count":6,"title":["Representing Hyper-arithmetical Sets by Equations over Sets of Integers"],"prefix":"10.1007","volume":"51","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,8,4]]},"reference":[{"key":"9352_CR1","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1016\/S0049-237X(08)71120-0","volume-title":"Handbook of Mathematical Logic","author":"P. Aczel","year":"1977","unstructured":"Aczel, P.: An introduction to inductive definitions. In: Barwise, J. (ed.) Handbook of Mathematical Logic, pp.\u00a0739\u2013783. North-Holland, Amsterdam (1977)"},{"issue":"1","key":"9352_CR2","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0304-3975(02)00232-3","volume":"293","author":"F. d\u2019Alessandro","year":"2003","unstructured":"d\u2019Alessandro, F., Sakarovitch, J.: The finite power property in free groups. Theor. Comput. Sci. 293(1), 55\u201382 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9352_CR3","series-title":"LNCS","first-page":"167","volume-title":"Mathematical Foundations of Computer Science (MFCS 1975)","author":"A.V. Anisimov","year":"1975","unstructured":"Anisimov, A.V.: Languages over free groups. In: Mathematical Foundations of Computer Science (MFCS 1975), Mari\u00e1nsk\u00e9 L\u00e1zn\u011b, September 1\u20135, 1975. LNCS, vol.\u00a032, pp.\u00a0167\u2013171 (1975)"},{"key":"9352_CR4","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"},{"issue":"2","key":"9352_CR5","doi-asserted-by":"crossref","first-page":"637","DOI":"10.2307\/2274706","volume":"56","author":"J.Y. Halpern","year":"1991","unstructured":"Halpern, J.Y.: Presburger arithmetic with unary predicates is $\\varPi ^{1}_{1}$ complete. J. Symb. Log. 56(2), 637\u2013642 (1991)","journal-title":"J. Symb. Log."},{"issue":"3","key":"9352_CR6","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":"9352_CR7","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":"9352_CR8","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":"9352_CR9","series-title":"LNCS","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 (ICALP 2008)","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. LNCS, vol.\u00a05126, pp.\u00a063\u201374 (2008)"},{"key":"9352_CR10","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.\u00a0577\u2013588 (2009)"},{"issue":"2","key":"9352_CR11","doi-asserted-by":"crossref","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)","journal-title":"Theory Comput. Syst."},{"key":"9352_CR12","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/978-3-642-15155-2_39","volume-title":"Mathematical Foundations of Computer Science (MFCS 2010)","author":"A. Je\u017c","year":"2010","unstructured":"Je\u017c, A., Okhotin, A.: Least and greatest solutions of equations over sets of integers. In: Mathematical Foundations of Computer Science (MFCS 2010), Brno, Czech Republic, 23\u201327 August 2010. LNCS, vol.\u00a06281, pp.\u00a0441\u2013452 (2010)"},{"issue":"4","key":"9352_CR13","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":"9352_CR14","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 (DLT 2007)","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.\u00a023\u201327 (2007)"},{"issue":"2","key":"9352_CR15","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1142\/S012905411100809X","volume":"22","author":"T. Lehtinen","year":"2011","unstructured":"Lehtinen, T., Okhotin, A.: On equations over sets of numbers and their limitations. Int. J. Found. Comput. Sci. 22(2), 377\u2013393 (2011)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9352_CR16","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 (DLT 2010)","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, 17\u201320 August 2010. LNCS, vol.\u00a06224, pp.\u00a0291\u2013302 (2010)"},{"issue":"3","key":"9352_CR17","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":"9352_CR18","volume-title":"Elementary Induction on Abstract Structures","author":"Y. Moschovakis","year":"1974","unstructured":"Moschovakis, Y.: Elementary Induction on Abstract Structures. North-Holland, Amsterdam (1974)"},{"issue":"4","key":"9352_CR19","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":"3","key":"9352_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."},{"issue":"4","key":"9352_CR21","first-page":"563","volume":"74","author":"A. Okhotin","year":"2006","unstructured":"Okhotin, A.: Computational universality in one-variable language equations. Fundam. Inform. 74(4), 563\u2013578 (2006)","journal-title":"Fundam. Inform."},{"issue":"3\u20134","key":"9352_CR22","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/j.jcss.2009.08.002","volume":"76","author":"A. Okhotin","year":"2010","unstructured":"Okhotin, A.: Decision problems for language equations. J. Comput. Syst. Sci. 76(3\u20134), 251\u2013266 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"9352_CR23","series-title":"IFIP","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/978-0-387-09680-3_15","volume-title":"IFIP International Conference on Theoretical Computer Science (TCS 2008)","author":"A. Okhotin","year":"2008","unstructured":"Okhotin, A., Rondogiannis, P.: On the expressive power of univariate equations over sets of natural numbers. In: IFIP International Conference on Theoretical Computer Science (TCS 2008), Milan, Italy, 8\u201310 September 2008. IFIP, vol.\u00a0273, pp.\u00a0215\u2013227 (2008)"},{"issue":"3","key":"9352_CR24","doi-asserted-by":"crossref","first-page":"325","DOI":"10.2307\/2270774","volume":"32","author":"J. Robinson","year":"1967","unstructured":"Robinson, J.: An introduction to hyperarithmetical functions. J. Symb. Log. 32(3), 325\u2013342 (1967)","journal-title":"J. Symb. Log."},{"key":"9352_CR25","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers Jr.","year":"1967","unstructured":"Rogers, H., Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967)"},{"issue":"1\u20133","key":"9352_CR26","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."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00224-011-9352-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T00:09:42Z","timestamp":1497917382000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9352-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8,4]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["9352"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9352-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,8,4]]}}}