{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T10:48:42Z","timestamp":1758278922476},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2009,4,14]],"date-time":"2009-04-14T00:00:00Z","timestamp":1239667200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Math Sci"],"published-print":{"date-parts":[[2009,5]]},"DOI":"10.1007\/s10958-009-9397-z","type":"journal-article","created":{"date-parts":[[2009,4,13]],"date-time":"2009-04-13T04:01:34Z","timestamp":1239595294000},"page":"605-614","source":"Crossref","is-referenced-by-count":11,"title":["Complexity of the identity checking problem for finite semigroups"],"prefix":"10.1007","volume":"158","author":[{"given":"J.","family":"Almeida","sequence":"first","affiliation":[]},{"given":"M. V.","family":"Volkov","sequence":"additional","affiliation":[]},{"given":"S. V.","family":"Goldberg","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,4,14]]},"reference":[{"key":"9397_CR1","first-page":"16","volume-title":"International Algebraic Conference Dedicated to the Centinenial of P. G. Kontorovich and the 70th Birthday of L. N. Shevrin, Abstracts","author":"J Almeida","year":"2005","unstructured":"J. Almeida, S. V. Plescheva, and M. V. Volkov, \u201cAn application of group generic implicit operators to the complexity of identity checking in finite semigroups,\u201d in: International Algebraic Conference Dedicated to the Centinenial of P. G. Kontorovich and the 70th Birthday of L. N. Shevrin, Abstracts, Ural State University, Ekaterinburg (2005), pp. 16\u201317."},{"issue":"2","key":"9397_CR2","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1142\/S0218196706002883","volume":"16","author":"J Almeida","year":"2006","unstructured":"J. Almeida and M. V. Volkov, \u201cSubword complexity of profinite words and subgroups of free profinite semigroups,\u201d Internat. J. Algebra Comput., 16, No. 2, 221\u2013258 (2006).","journal-title":"Internat. J. Algebra Comput."},{"issue":"2","key":"9397_CR3","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S0097539798345944","volume":"30","author":"C Bergman","year":"2000","unstructured":"C. Bergman and G. Slutzki, \u201cComplexity of some problems concerning varieties and quasi-varieties of algebras,\u201d SIAM J. Comput., 30, No. 2, 359\u2013382 (2000).","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9397_CR4","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1006\/jsco.1993.1004","volume":"15","author":"S Burris","year":"1993","unstructured":"S. Burris and J. Lawrence, \u201cThe equivalence problem for finite rings,\u201d J. Symbolic Comput., 15, No. 1, 67\u201371 (1993).","journal-title":"J. Symbolic Comput."},{"issue":"4","key":"9397_CR5","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1007\/s00012-004-1895-8","volume":"52","author":"S Burris","year":"2005","unstructured":"S. Burris and J. Lawrence, \u201cResults on the equivalence problem for finite groups,\u201d Algebra Universalis, 52, No. 4, 495\u2013500 (2005).","journal-title":"Algebra Universalis"},{"issue":"1","key":"9397_CR6","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF02195732","volume":"15","author":"CC Edmunds","year":"1977","unstructured":"C. C. Edmunds, \u201cOn certain finitely based varieties of semigroups,\u201d Semigroup Forum, 15, No. 1, 21\u201339 (1977).","journal-title":"Semigroup Forum"},{"key":"9397_CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco (1979)."},{"issue":"3","key":"9397_CR8","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1112\/blms\/bdm030","volume":"39","author":"G Horv\u00e1th","year":"2007","unstructured":"G. Horv\u00e1th, J. Lawrence, L. M\u00e9rai, and Cs. Szab\u00f3, \u201cThe complexity of the equivalence problem for nonsolvable groups,\u201d Bull. London Math. Soc., 39, No. 3, 433\u2013438 (2007).","journal-title":"Bull. London Math. Soc."},{"issue":"5","key":"9397_CR9","doi-asserted-by":"crossref","first-page":"931","DOI":"10.1142\/S0218196706003256","volume":"16","author":"G Horv\u00e1th","year":"2006","unstructured":"G. Horv\u00e1th and Cs. Szab\u00f3, \u201cThe complexity of checking identities over finite groups,\u201d Internat. J. Algebra Comput., 16, No. 5, 931\u2013939 (2006).","journal-title":"Internat. J. Algebra Comput."},{"issue":"5","key":"9397_CR10","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1016\/S0747-7171(08)80053-3","volume":"10","author":"HB Hunt III","year":"1990","unstructured":"H. B. Hunt III and R. E. Stearns, \u201cThe complexity of equivalence for commutative rings,\u201d J. Symbolic Comput., 10, No. 5, 411\u2013436 (1990).","journal-title":"J. Symbolic Comput."},{"issue":"1","key":"9397_CR11","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1142\/S0218196706002846","volume":"16","author":"M Jackson","year":"2006","unstructured":"M. Jackson and R. McKenzie, \u201cInterpreting graph colorability in finite semigroups,\u201d Internat. J. Algebra Comput., 16, No. 1, 119\u2013140 (2006).","journal-title":"Internat. J. Algebra Comput."},{"issue":"1","key":"9397_CR12","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1090\/S0002-9939-1952-0047584-3","volume":"3","author":"J Kalicki","year":"1952","unstructured":"J. Kalicki, \u201cOn comparison of finite algebras,\u201d Proc. Amer. Math. Soc., 3, No. 1, 36\u201340 (1952).","journal-title":"Proc. Amer. Math. Soc."},{"key":"9397_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-9964-6","volume-title":"Fundamentals of the Theory of Groups","author":"MI Kargapolov","year":"1979","unstructured":"M. I. Kargapolov and J. I. Merzljakov, Fundamentals of the Theory of Groups, Springer, New York\u2013Berlin (1979)."},{"issue":"4\u20135","key":"9397_CR14","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1142\/S0218196795000227","volume":"5","author":"OG Kharlampovich","year":"1995","unstructured":"O. G. Kharlampovich and M. V. Sapir, \u201cAlgorithmic problems in varieties,\u201d Internat. J. Algebra Comput., 5, Nos. 4\u20135, 379\u2013602 (1995).","journal-title":"Internat. J. Algebra Comput."},{"issue":"4","key":"9397_CR15","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1142\/S0218196704001840","volume":"14","author":"A Kisielewicz","year":"2004","unstructured":"A. Kisielewicz, \u201cComplexity of semigroup identity checking,\u201d Internat. J. Algebra Comput., 14, No. 4, 455\u2013464 (2004).","journal-title":"Internat. J. Algebra Comput."},{"key":"9397_CR16","doi-asserted-by":"crossref","unstructured":"O. Kl\u00edma, \u201cComplexity issues of checking identities in finite monoids,\u201d Semigroup Forum, accepted.","DOI":"10.1007\/s00233-009-9180-y"},{"key":"9397_CR17","unstructured":"M. Kozik, \u201cOn some complexity problems in finite algebras,\u201d PhD Thesis, Vanderbilt University, Nashville (2004)."},{"issue":"8","key":"9397_CR18","doi-asserted-by":"crossref","first-page":"1635","DOI":"10.1142\/S0218196707004335","volume":"17","author":"M Kozik","year":"2007","unstructured":"M. Kozik, \u201cComputationally and algebraically complex finite algebra membership problems,\u201d Internat. J. Algebra Comput., 17, No. 8, 1635\u20131666 (2007).","journal-title":"Internat. J. Algebra Comput."},{"key":"9397_CR19","unstructured":"M. Kozik, \u201cVarietal membership problem is 2-EXPTIME complete,\u201d submitted."},{"key":"9397_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61896-3","volume-title":"Combinatorial Group Theory","author":"RC Lyndon","year":"1977","unstructured":"R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, Springer-Verlag, Berlin\u2013Heidelberg\u2013New York (1977)."},{"key":"9397_CR21","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1994","unstructured":"C. H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading (1994)."},{"key":"9397_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-2215-3","volume-title":"Varieties of Formal Languages","author":"J-E Pin","year":"1986","unstructured":"J.-E. Pin, Varieties of Formal Languages, Plenum, New York (1986)."},{"key":"9397_CR23","unstructured":"S. V. Plescheva and V. V\u00e9rtesi, \u201cComplexity of the identity checking problem in a 0-simple semigroup,\u201d Izv. Ural. Gos. Univ., No. 43, 72\u2013102 (2006)."},{"issue":"2","key":"9397_CR24","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1142\/S0218196705002293","volume":"15","author":"S Seif","year":"2005","unstructured":"S. Seif, \u201cThe Perkins semigroup has co-NP-complete term-equivalence problem,\u201d Internat. J. Algebra Comput., 15, No. 2, 317\u2013326 (2005).","journal-title":"Internat. J. Algebra Comput."},{"issue":"2","key":"9397_CR25","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s00233-005-0510-4","volume":"72","author":"S Seif","year":"2006","unstructured":"S. Seif and Cs. Szab\u00f3, \u201cComputational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields,\u201d Semigroup Forum, 72, No. 2, 207\u2013222 (2006).","journal-title":"Semigroup Forum"},{"key":"9397_CR26","first-page":"174","volume":"1","author":"EP Simel\u2019gor","year":"1974","unstructured":"E. P. Simel\u2019gor, \u201cIdentities in a finite symmetric semigroup,\u201d Modern Algebra, 1, 174\u2013188 (1974).","journal-title":"Modern Algebra"},{"issue":"12","key":"9397_CR27","doi-asserted-by":"crossref","first-page":"3689","DOI":"10.1090\/S0002-9939-04-07488-X","volume":"132","author":"Cs Szab\u00f3","year":"2004","unstructured":"Cs. Szab\u00f3 and V. V\u00e9rtesi, \u201cThe complexity of the word-problem for finite matrix rings,\u201d Proc. Amer. Math. Soc., 132, No. 12, 3689\u20133695 (2004).","journal-title":"Proc. Amer. Math. Soc."},{"issue":"4","key":"9397_CR28","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/s00012-004-1873-1","volume":"51","author":"Cs Szab\u00f3","year":"2004","unstructured":"Cs. Szab\u00f3 and V. V\u00e9rtesi, \u201cThe complexity of checking identities for finite matrix rings,\u201d Algebra Universalis, 51, No. 4, 439\u2013445 (2004).","journal-title":"Algebra Universalis"},{"key":"9397_CR29","unstructured":"Cs. Szab\u00f3 and V. V\u00e9rtesi, \u201cThe identity checking problem in finite rings,\u201d submitted."},{"issue":"6","key":"9397_CR30","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1142\/S0218196702001085","volume":"12","author":"Z Sz\u00e9kely","year":"2002","unstructured":"Z. Sz\u00e9kely, \u201cComputational complexity of the finite algebra membership problem for varieties,\u201d Internat. J. Algebra Comput., 12, No. 6, 811\u2013823 (2002).","journal-title":"Internat. J. Algebra Comput."},{"key":"9397_CR31","unstructured":"P. Tesson, \u201cComputational complexity questions related to finite monoids and semigroups,\u201d PhD Thesis, McGill University, Montr\u00e9al (2003)."}],"container-title":["Journal of Mathematical Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10958-009-9397-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10958-009-9397-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10958-009-9397-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T10:09:28Z","timestamp":1559470168000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10958-009-9397-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,14]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["9397"],"URL":"https:\/\/doi.org\/10.1007\/s10958-009-9397-z","relation":{},"ISSN":["1072-3374","1573-8795"],"issn-type":[{"value":"1072-3374","type":"print"},{"value":"1573-8795","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4,14]]}}}