{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T15:13:31Z","timestamp":1770909211046,"version":"3.50.1"},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":8046,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1992,3]]},"abstract":"<jats:p>In 1947 E. Post [28] and A. A. Markov [18] independently proved the undecidability of the word problem (or the problem of deducibility of relations) for semigroups. In 1968 V. L. Murskil [23] proved the undecidability of the identity problem (or the problem of deducibility of identities) in semigroups.<\/jats:p><jats:p>If we slightly generalize the statement of these results we can state many related results in the literature and state our new results proved here. Let <jats:italic>V<\/jats:italic> denote either a (Birkhoff) variety of semigroups or groups or a pseudovariety of finite semigroups. By a very well-known theorem a (Birkhoff) variety is defined by equations or equivalently closed under substructure, surmorphisms and all products; see [7]. It is also well known that <jats:italic>V<\/jats:italic> is a pseudovariety of finite semigroups iff <jats:italic>V<\/jats:italic> is closed under substructure, surmorphism and finite products, or, equivalently, determined eventually by equations <jats:italic>w<\/jats:italic><jats:sub>1<\/jats:sub> = <jats:italic>w<\/jats:italic><jats:sub>1<\/jats:sub>\u2032, <jats:italic>w<\/jats:italic><jats:sub>2<\/jats:sub> = <jats:italic>w<\/jats:italic><jats:sub>2<\/jats:sub>\u2032, <jats:italic>w<\/jats:italic><jats:sub>3<\/jats:sub> = <jats:italic>w<\/jats:italic><jats:sub>3<\/jats:sub>\u2032,\u2026 (where the finite semigroup <jats:italic>S<\/jats:italic> eventually satisfies these equations iff there exists an <jats:italic>n<\/jats:italic>, depending on <jats:italic>S<\/jats:italic>, such that <jats:italic>S<\/jats:italic> satisfies <jats:italic>W<jats:sub>j<\/jats:sub><\/jats:italic> = <jats:italic>W<jats:sub>j<\/jats:sub><\/jats:italic>\u2032 for <jats:italic>j<\/jats:italic> \u2265 <jats:italic>n<\/jats:italic>). See [8] and [29]. All semigroups form a variety while all finite semigroups form a pseudovariety.<\/jats:p><jats:p>We now consider a table (see the next page). In it, for example, the box denoting the \u201cword\u201d (identity) problem for the psuedovariety <jats:italic>V<\/jats:italic>\u201d means, given a finite set of relations (identities) <jats:italic>E<\/jats:italic> and a relation (identity) <jats:italic>u<\/jats:italic> = \u03bd, the problem of whether it is decidable that <jats:italic>E<\/jats:italic> implies <jats:italic>u<\/jats:italic> = \u03bd inside <jats:italic>V<\/jats:italic>.<\/jats:p>","DOI":"10.2307\/2275184","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:43:45Z","timestamp":1146955425000},"page":"179-192","source":"Crossref","is-referenced-by-count":41,"title":["Undecidability of the identity problem for finite semigroups"],"prefix":"10.1017","volume":"57","author":[{"given":"Douglas","family":"Albert","sequence":"first","affiliation":[]},{"given":"Robert","family":"Baldinger","sequence":"additional","affiliation":[]},{"given":"John","family":"Rhodes","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200023252_ref038","first-page":"1","article-title":"Identities of semigroups","volume":"29","author":"Shevrin","year":"1985","journal-title":"Izvestiya Vysshikh Uchebnykh Zavedeni\u01d0 Matematika"},{"key":"S0022481200023252_ref026","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(64)90004-3"},{"key":"S0022481200023252_ref002","first-page":"105","volume-title":"Monoids and semigroups with applications (proceedings of the Berkeley workshop on monoids","author":"Almeida","year":"1991"},{"key":"S0022481200023252_ref020","first-page":"144","article-title":"Word problems in varieties of semigroups, rings and Lie algebras","volume":"27","author":"Mel'nichuk","year":"1986","journal-title":"Sibirski\u01d0 Matematicheski\u01d0 Zhurnal"},{"key":"S0022481200023252_ref030","unstructured":"Rhodes J. , The presentation lemma for complexity of finite semigroups, unpublished manuscript, 1974."},{"key":"S0022481200023252_ref032","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-3839-7_20"},{"key":"S0022481200023252_ref029","doi-asserted-by":"publisher","DOI":"10.1007\/BF02483902"},{"key":"S0022481200023252_ref018","first-page":"587","article-title":"On the impossibility of certain algorithms in the theory of associative systems","volume":"55","author":"Markov","year":"1947","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200023252_ref001","unstructured":"Albert D. and Rhodes J. , Undecidability of the identity problem for finite semigroups with applications, preprint, 1986."},{"key":"S0022481200023252_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(86)90136-2"},{"key":"S0022481200023252_ref036","unstructured":"Sapir M. V. , private communication."},{"key":"S0022481200023252_ref016","first-page":"3","article-title":"Identity relations in varieties of quasigroups","volume":"69","author":"Mal'cev","year":"1966","journal-title":"Matematicheski\u01d0 Sbornik"},{"key":"S0022481200023252_ref035","doi-asserted-by":"publisher","DOI":"10.1007\/BF01978400"},{"key":"S0022481200023252_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF02572269"},{"key":"S0022481200023252_ref039","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(87)90108-3"},{"key":"S0022481200023252_ref028","first-page":"1","volume":"12","author":"Post","year":"1947","journal-title":"Recursive unsolvability of a problem of Thue"},{"key":"S0022481200023252_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/S1385-7258(54)50061-2"},{"key":"S0022481200023252_ref007","volume-title":"A course in universal algebra","author":"Burris","year":"1980"},{"key":"S0022481200023252_ref008","volume-title":"Automata, languages and machines","volume":"B","author":"Eilenberg","year":"1976"},{"key":"S0022481200023252_ref011","first-page":"184","volume":"49","author":"Gurevich","year":"1984","journal-title":"The word problem for cancellation semigroups with zeros"},{"key":"S0022481200023252_ref012","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700016748"},{"key":"S0022481200023252_ref014","first-page":"852","article-title":"A finitely presented solvable group with insoluble word problem","volume":"45","author":"Kharlampovich","year":"1981","journal-title":"Izvestiya Akademii Nauk SSSR Seriya Matematicheskaya"},{"key":"S0022481200023252_ref015","first-page":"814","article-title":"Identities and some algorithmic problems in groups","volume":"244","author":"Kle\u01d0man","year":"1979","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200023252_ref017","first-page":"49","article-title":"On homomorphisms onto finite groups","volume":"18","author":"Mal'cev","year":"1958","journal-title":"Ivanovski\u01d0 Gosudarstvenny\u01d0 Pedagogicheski\u01d0 Institut Uchenye Zapiski"},{"key":"S0022481200023252_ref031","first-page":"197","volume-title":"Proceedings of the Marquette conference on semigroups","author":"Rhodes","year":"1984"},{"key":"S0022481200023252_ref019","doi-asserted-by":"publisher","DOI":"10.1007\/BF02071790"},{"key":"S0022481200023252_ref021","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"key":"S0022481200023252_ref023","first-page":"663","article-title":"Some examples of varieties of semigroups","volume":"3","author":"Murski\u01d0","year":"1968","journal-title":"Matematicheskie Zametki"},{"key":"S0022481200023252_ref006","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-8.4.493"},{"key":"S0022481200023252_ref024","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-88599-0"},{"key":"S0022481200023252_ref025","volume":"44","author":"Novikov","year":"1955","journal-title":"On the algorithmic unsolubility of the word problem in group theory, Trudy Matematicheskogo Instituta imeni V. A. Steklova"},{"key":"S0022481200023252_ref027","volume-title":"Vari\u00e9t\u00e9s de langages formels","author":"Pin","year":"1984"},{"key":"S0022481200023252_ref010","first-page":"25","article-title":"The word problem for certain classes of semigroups","volume":"5","author":"Gurevich","year":"1966","journal-title":"Algebra i Logika Seminar"},{"key":"S0022481200023252_ref033","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200023252_ref034","first-page":"206","volume-title":"Semigroups and monoids with applications (proceedings of the Berkeley workshop on monoids","author":"Sapir","year":"1991"},{"key":"S0022481200023252_ref004","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1979.85.261"},{"key":"S0022481200023252_ref013","unstructured":"Kharlampovich O. G. , Algorithmic and other combinatorial problems for groups and Lie algebras, Ph. D. thesis, Department of Mathematics, Ural State University, Sverdlovsk, 1983. (Russian)."},{"key":"S0022481200023252_ref037","doi-asserted-by":"publisher","DOI":"10.1007\/BF01735740"},{"key":"S0022481200023252_ref040","first-page":"89","volume-title":"Semigroups and monoids with applications (proceedings of the Berkeley workshop on monoids","author":"Weil","year":"1991"},{"key":"S0022481200023252_ref022","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-44-01101-4"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200023252","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T22:32:47Z","timestamp":1558045967000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200023252\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,3]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1992,3]]}},"alternative-id":["S0022481200023252"],"URL":"https:\/\/doi.org\/10.2307\/2275184","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,3]]}}}