{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T12:27:55Z","timestamp":1765369675829},"reference-count":35,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2020,9,28]],"date-time":"2020-09-28T00:00:00Z","timestamp":1601251200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This note addresses the issue as to which ceers can be realized by word problems of computably enumerable (or, simply, c.e.) structures (such as c.e.\u00a0semigroups, groups, and rings), where being realized means to fall in the same reducibility degree (under the notion of reducibility for equivalence relations usually called \u201ccomputable reducibility\u201d), or in the same isomorphism type (with the isomorphism induced by a computable function), or in the same strong isomorphism type (with the isomorphism induced by a computable permutation of the natural numbers). We observe, e.g., that every ceer is isomorphic to the word problem of some c.e.\u00a0semigroup, but (answering a question of Gao and Gerdes) not every ceer is in the same reducibility degree of the word problem of some finitely presented semigroup, nor is it in the same reducibility degree of some non\u2010periodic semigroup. We also show that the ceer provided by provable equivalence of Peano Arithmetic is in the same strong isomorphism type as the word problem of some non\u2010commutative and non\u2010Boolean c.e.\u00a0ring.<\/jats:p>","DOI":"10.1002\/malq.202000021","type":"journal-article","created":{"date-parts":[[2020,9,29]],"date-time":"2020-09-29T06:45:39Z","timestamp":1601361939000},"page":"341-354","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Word problems and ceers"],"prefix":"10.1002","volume":"66","author":[{"given":"Valentino","family":"Delle Rose","sequence":"first","affiliation":[{"name":"Dipartimento di Ingegneria Informatica e Scienze Matematiche Universit\u00e0 Degli Studi di Siena  San Niccol\u00f2, via Roma, 56, 53100 Siena Italy"}]},{"given":"Luca","family":"San Mauro","sequence":"additional","affiliation":[{"name":"Institute of Discrete Mathematics and Geometry Technische Universit\u00e4t Wien  Wiedner Hauptstra\u00dfe 8\u201010, 1040 Wien Austria"}]},{"given":"Andrea","family":"Sorbi","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria Informatica e Scienze Matematiche Universit\u00e0 Degli Studi di Siena  San Niccol\u00f2, via Roma, 56, 53100 Siena Italy"}]}],"member":"311","published-online":{"date-parts":[[2020,9,28]]},"reference":[{"issue":"1","key":"e_1_2_6_2_1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1017\/jsl.2019.39","article-title":"On isomorphism classes of computably enumerable equivalence relations","volume":"85","author":"Andrews U.","year":"2020","journal-title":"J. Symb. Log."},{"key":"e_1_2_6_3_1","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1007\/978-3-319-50062-1_25","volume-title":"Computability and Complexity. Essays Dedicated to Rodney G. Downey on the Occasion of his 60th Birthday","author":"Andrews U.","year":"2017"},{"key":"e_1_2_6_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2013.8"},{"key":"e_1_2_6_5_1","doi-asserted-by":"publisher","DOI":"10.3233\/COM-180098"},{"key":"e_1_2_6_6_1","article-title":"Effective inseparability, lattices, and pre\u2010ordering relations","author":"Andrews U.","journal-title":"to appear in: Rev. Symb. Log."},{"key":"e_1_2_6_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273443"},{"key":"e_1_2_6_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01094865"},{"issue":"2","key":"e_1_2_6_9_1","doi-asserted-by":"crossref","first-page":"207","DOI":"10.2307\/1970103","article-title":"The word problem","volume":"70","author":"Boone W. W.","year":"1959","journal-title":"Ann. Math."},{"issue":"3","key":"e_1_2_6_10_1","doi-asserted-by":"crossref","first-page":"520","DOI":"10.2307\/1970478","article-title":"Word problems and recursively enumerable degrees of unsolvability. A first paper on Thue systems","volume":"83","author":"Boone W. W.","year":"1966","journal-title":"Ann. Math."},{"issue":"1","key":"e_1_2_6_11_1","doi-asserted-by":"crossref","first-page":"49","DOI":"10.2307\/1970530","article-title":"Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups","volume":"84","author":"Boone W. W.","year":"1966","journal-title":"Ann. Math."},{"key":"e_1_2_6_12_1","doi-asserted-by":"crossref","first-page":"389","DOI":"10.2307\/1970762","article-title":"Word problems and recursively enumerable degrees of unsolvability. An emendation","volume":"94","author":"Boone W. W.","year":"1971","journal-title":"Ann. Math."},{"key":"e_1_2_6_13_1","volume-title":"A Course in Universal Algebra","author":"Burris S.","year":"2012"},{"issue":"4","key":"e_1_2_6_14_1","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1112\/plms\/s3-14.4.633","article-title":"Finitely presented groups with word problems of arbitrary degrees of insolubility","volume":"3","author":"J. Clapham C. R.","year":"1964","journal-title":"Proc. Lond. Math. Soc."},{"key":"e_1_2_6_15_1","volume-title":"The Algebraic Theory of Semigroups. Vol. I, Mathematical Surveys","author":"Clifford A. H.","year":"1961"},{"key":"e_1_2_6_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-8399-1"},{"key":"e_1_2_6_17_1","unstructured":"V. DelleRose L. SanMauro andA.Sorbi A note on the category of equivalence relations submitted."},{"key":"e_1_2_6_18_1","volume-title":"\u0422\u0435\u043e\u0440\u0438\u044f \u043d\u0443\u043c\u0435\u0440\u0430\u0446\u0438\u0439, \u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u041b\u043e\u0433\u0438\u043a\u0430 \u0438 \u041e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f \u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438","author":"Ershov Y. L.","year":"1977"},{"issue":"2","key":"e_1_2_6_19_1","first-page":"1733","article-title":"Degrees of unsolvability of the problem of identity in finitely presented groups","volume":"3","author":"Fridman A. A.","year":"1962","journal-title":"Soviet. Math."},{"key":"e_1_2_6_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2015.11"},{"key":"e_1_2_6_21_1","doi-asserted-by":"publisher","DOI":"10.3233\/COM-180100"},{"key":"e_1_2_6_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010521410739"},{"key":"e_1_2_6_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2014.04.001"},{"key":"e_1_2_6_24_1","volume-title":"Fundamentals of semigroup theory","author":"Howie J. M.","year":"1995"},{"key":"e_1_2_6_25_1","first-page":"1","volume-title":"Sailing Routes in the World of Computation, 14th Conference on Computability in Europe, CiE 2018","author":"Khoussainov B.","year":"2018"},{"key":"e_1_2_6_26_1","first-page":"172","article-title":"\u041e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0438\u043d\u0434\u0438\u0432\u0438\u0434\u0443\u0430\u043b\u044c\u043d\u044b\u0445 \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0430 \u0432 \u043f\u043e\u043b\u0443\u0433\u0440\u0443\u043f\u043f\u0430\u0445","volume":"9","author":"Litvinceva Z. K.","year":"1970","journal-title":"Algebra Log."},{"key":"e_1_2_6_27_1","volume-title":"Group\u2010Theoretic Decision Problems and their Classification","author":"Miller C. F.","year":"1971"},{"issue":"4","key":"e_1_2_6_28_1","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/BF00284977","article-title":"Relative precomplete numerations and arithmetic","volume":"11","author":"Montagna F.","year":"1982","journal-title":"J. Philos. Log."},{"key":"e_1_2_6_29_1","doi-asserted-by":"publisher","DOI":"10.2307\/2274228"},{"key":"e_1_2_6_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129516000335"},{"key":"e_1_2_6_31_1","first-page":"3","article-title":"\u041e\u0431 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043d\u0435\u0440\u0430\u0437\u0440\u0435\u0448\u0438\u043c\u043e\u0441\u0442\u0438 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0430 \u0441\u043b\u043e\u0432 \u0432 \u0442\u0435\u043e\u0440\u0438\u0438 \u0433\u0440\u0443\u043f\u043f","volume":"44","author":"Novikov P. S.","year":"1955","journal-title":"Trudy Mat. Inst. Steklov"},{"key":"e_1_2_6_32_1","doi-asserted-by":"crossref","first-page":"141","DOI":"10.4064\/fm-61-2-141-163","article-title":"Deduction preserving \u201cRecursive Isomorphisms\u201d between theories","volume":"61","author":"Pour\u2010El M. B.","year":"1967","journal-title":"Fundam. Math."},{"key":"e_1_2_6_33_1","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/978-1-4615-0755-0_14","volume-title":"Computability and Models, Perspectives East and West","author":"Selivanov V.","year":"2003"},{"key":"e_1_2_6_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19960420107"},{"key":"e_1_2_6_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19650110210"},{"key":"e_1_2_6_36_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-75462-3","volume-title":"Logical Number Theory I: An Introduction","author":"Smory\u0144ski C.","year":"1991"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.202000021","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/malq.202000021","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.202000021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T13:40:45Z","timestamp":1693834845000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.202000021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,28]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["10.1002\/malq.202000021"],"URL":"https:\/\/doi.org\/10.1002\/malq.202000021","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,28]]},"assertion":[{"value":"2020-03-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-22","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}