{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T15:48:53Z","timestamp":1772812133867,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Order"],"published-print":{"date-parts":[[2008,8]]},"DOI":"10.1007\/s11083-008-9083-7","type":"journal-article","created":{"date-parts":[[2008,8,29]],"date-time":"2008-08-29T09:57:43Z","timestamp":1220003863000},"page":"177-194","source":"Crossref","is-referenced-by-count":40,"title":["Word Problem of the Perkins Semigroup via Directed Acyclic Graphs"],"prefix":"10.1007","volume":"25","author":[{"given":"Sergey","family":"Kitaev","sequence":"first","affiliation":[]},{"given":"Steve","family":"Seif","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,8,30]]},"reference":[{"key":"9083_CR1","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1006\/jsco.1993.1004","volume":"15","author":"S. Burris","year":"1993","unstructured":"Burris, S., Lawrence, J.: The equivalence problem for finite rings. J. Symbol. Comput. 15, 67\u201371 (1993)","journal-title":"J. Symbol. Comput."},{"issue":"4","key":"9083_CR2","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1007\/s00012-004-1895-8","volume":"52","author":"S. Burris","year":"2004","unstructured":"Burris, S., Lawrence, J.: Results on the equivalence problem for finite groups. Alg. Univ. 52(4), 495\u2013500 (2004)","journal-title":"Alg. Univ."},{"key":"9083_CR3","first-page":"153","volume-title":"Proc. Internat. Conf. Theory of Groups","author":"G. Higman","year":"1965","unstructured":"Higman, G.: The orders of relatively free groups. In: Proc. Internat. Conf. Theory of Groups, pp.\u00a0153\u2013165. Austral. Nat. Univ. Canberra (1965)"},{"key":"9083_CR4","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1112\/blms\/bdm030","volume":"39","author":"G. Horvath","year":"2007","unstructured":"Horvath, G., Lawrence, J., Merai, L., Szabo, C.: The complexity of the equivalence problem for non-solvable groups. Bull. Lond. Math. Soc. 39, 253\u2013260 (2007)","journal-title":"Bull. Lond. Math. Soc."},{"key":"9083_CR5","unstructured":"64 Problems in Universal Algebra: workshop notes from A Course In Tame Congruence Theory, Budapest (2001). 2\u201313 July. http:\/\/www.math.u-szeged.hu\/confer\/algebra\/2001\/64problems.ps"},{"key":"9083_CR6","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s000120050132","volume":"42","author":"K.A. Kearnes","year":"1999","unstructured":"Kearnes, K.A.: Congruence modular varieties with small free spectra. Algebra Universalis 42, 165\u2013181 (1999)","journal-title":"Algebra Universalis"},{"key":"9083_CR7","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1142\/S0218196704001840","volume":"14","author":"A. Kisielewicz","year":"2004","unstructured":"Kisielewicz, A.: Complexity of identity checking for semigroups. Int. J. Algebra Comput. 14, 455\u2013464 (2004)","journal-title":"Int. J. Algebra Comput."},{"key":"9083_CR8","first-page":"45","volume":"13","author":"S. Kitaev","year":"2008","unstructured":"Kitaev, S., Pyatkin, A.: On representable graphs. Automata, Languages and Combinatorics 13, 45\u201354 (2008). http:\/\/www.ru.is\/kennarar\/sergey\/index_files\/Papers\/repgr.pdf","journal-title":"Automata, Languages and Combinatorics"},{"key":"9083_CR9","unstructured":"Klima, O.: Complexity issues of checking identities in finite monoids. http:\/\/www.math.muni.cz\/~klima\/Math\/coNPidcheck.ps"},{"issue":"6","key":"9083_CR10","doi-asserted-by":"crossref","first-page":"1084","DOI":"10.4153\/CJM-1990-058-9","volume":"42","author":"S.W. Margolis","year":"1990","unstructured":"Margolis, S.W., Meakin, J.C., Stephen, J.: Free objects in certain varieties of inverse semigroups. Canad. J. Math. 42(6), 1084\u20131097 (1990)","journal-title":"Canad. J. Math."},{"key":"9083_CR11","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1093\/qmath\/14.1.46","volume":"14","author":"P.M. Neumann","year":"1963","unstructured":"Neumann, P.M.: Some indecomposable varieties of groups. Quart J. Math. Oxford 14, 46\u201358 (1963)","journal-title":"Quart J. Math. Oxford"},{"key":"9083_CR12","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/0021-8693(69)90058-1","volume":"11","author":"P. Perkins","year":"1969","unstructured":"Perkins, P.: Bases for equational theories of semigroups. J. Algebra 11, 298\u2013314 (1969)","journal-title":"J. Algebra"},{"issue":"1","key":"9083_CR13","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1112\/jlms\/s2-39.1.102","volume":"39","author":"N.R. Reilly","year":"1989","unstructured":"Reilly, N.R.: Free combinatorial strict inverse semigroups. J. London Math. Soc. (2), 39(1), 102\u2013120 (1989)","journal-title":"J. London Math. Soc. (2)"},{"issue":"2","key":"9083_CR14","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1142\/S0218196705002293","volume":"15","author":"S. Seif","year":"2005","unstructured":"Seif, S.: The Perkins Semigroup has Co-NP-complete term-equivalence problem. Int. J. Alg. Comp. (IJAC) 15(2), 317\u2013326 (2005)","journal-title":"Int. J. Alg. Comp. (IJAC)"},{"issue":"5","key":"9083_CR15","doi-asserted-by":"crossref","first-page":"1162","DOI":"10.1016\/j.jpaa.2007.09.008","volume":"212","author":"S. Seif","year":"2008","unstructured":"Seif, S.: Monoids with sub-log-exponential free spectra. J. Pure and Appl. Algebra 212(5), 1162\u20131174 (2008)","journal-title":"J. Pure and Appl. Algebra"},{"key":"9083_CR16","unstructured":"Seif, S.: Letter-uniform words and their graphs (manuscript)"},{"issue":"2","key":"9083_CR17","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s00233-005-0510-4","volume":"72","author":"S. Seif","year":"2006","unstructured":"Seif, S., Szabo, C.: Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields. Semigroup Forum 72(2), 207\u2013222 (2006)","journal-title":"Semigroup Forum"},{"issue":"1","key":"9083_CR18","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/s00233-006-0672-8","volume":"75","author":"S. Seif","year":"2007","unstructured":"Seif, S., Wood, J.: Asymptotic growth of free spectra of band monoids. Semigroup Forum 75(1), 77\u201394 (2007)","journal-title":"Semigroup Forum"},{"issue":"12","key":"9083_CR19","doi-asserted-by":"crossref","first-page":"3689","DOI":"10.1090\/S0002-9939-04-07488-X","volume":"132","author":"C. Szabo","year":"2004","unstructured":"Szabo, C., Vertesi, V.: The complexity of the word-problem for finite matrix rings. Proc. Amer. Math. Soc. 132(12), 3689\u20133695 (2004)","journal-title":"Proc. Amer. Math. Soc."},{"issue":"4","key":"9083_CR20","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/s00012-004-1873-1","volume":"51","author":"C. Szabo","year":"2004","unstructured":"Szabo, C., Vertesi, V.: The complexity of checking identities for finite matrix rings. Alg.Univ. 51(4), 439\u2013445 (2004)","journal-title":"Alg.Univ."},{"issue":"1\u20132","key":"9083_CR21","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s11225-005-0356-5","volume":"78","author":"M. Volkov","year":"2004","unstructured":"Volkov, M.: Checking Identities in a finite semigroup may be computationally hard. Studia Logica 78(1\u20132), 349\u2013356 (2004)","journal-title":"Studia Logica"}],"container-title":["Order"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-008-9083-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11083-008-9083-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-008-9083-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T05:12:12Z","timestamp":1559365932000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11083-008-9083-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["9083"],"URL":"https:\/\/doi.org\/10.1007\/s11083-008-9083-7","relation":{},"ISSN":["0167-8094","1572-9273"],"issn-type":[{"value":"0167-8094","type":"print"},{"value":"1572-9273","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}