{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T12:36:32Z","timestamp":1765370192405},"reference-count":33,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","funder":[{"name":"National Center for Artificial Intelligence CENIA","award":["FB210017"],"award-info":[{"award-number":["FB210017"]}]},{"name":"Austrian Science Fund","award":["P 36304-N"],"award-info":[{"award-number":["P 36304-N"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:p> We contribute to a recent research program which aims at revisiting the study of the complexity of word problems, a major area of research in combinatorial algebra, through the lens of the theory of computably enumerable equivalence relations (ceers), which has considerably grown in recent times. To pursue our analysis, we rely on the most popular way of assessing the complexity of ceers, that is via computable reducibility on equivalence relations, and its corresponding degree structure (the [Formula: see text]-degrees). On the negative side, building on previous work of Kasymov and Khoussainov, we individuate a collection of [Formula: see text]-degrees of ceers which cannot be realized by the word problem of any finitely generated algebra of finite type. On the positive side, we show that word problems of finitely generated semigroups realize a collection of [Formula: see text]-degrees which embeds rich structures and is large in several reasonable ways. <\/jats:p>","DOI":"10.1142\/s0218196723500339","type":"journal-article","created":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T09:48:57Z","timestamp":1684057737000},"page":"751-768","source":"Crossref","is-referenced-by-count":3,"title":["Classifying word problems of finitely generated algebras via computable reducibility"],"prefix":"10.1142","volume":"33","author":[{"given":"Valentino","family":"Delle Rose","sequence":"first","affiliation":[{"name":"National Center for Artificial Intelligence (CENIA), Chile"}]},{"given":"Luca","family":"San Mauro","sequence":"additional","affiliation":[{"name":"Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Austria"}]},{"given":"Andrea","family":"Sorbi","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria Informatica e Scienze Matematiche, Universit\u00e0 Degli Studi di Siena, I-53100 Siena, Italy"}]}],"member":"219","published-online":{"date-parts":[[2023,6,21]]},"reference":[{"key":"S0218196723500339BIB001","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1007\/978-3-319-50062-1_25","volume-title":"Computability and Complexity","author":"Andrews U.","year":"2017"},{"issue":"3","key":"S0218196723500339BIB002","doi-asserted-by":"crossref","first-page":"193","DOI":"10.3233\/COM-180098","volume":"8","author":"Andrews U.","year":"2019","journal-title":"Computability"},{"issue":"3","key":"S0218196723500339BIB003","doi-asserted-by":"crossref","first-page":"1260","DOI":"10.1017\/jsl.2022.14","volume":"87","author":"Andrews U.","year":"2022","journal-title":"J. Symbolic Logic"},{"issue":"8","key":"S0218196723500339BIB004","doi-asserted-by":"crossref","first-page":"102811","DOI":"10.1016\/j.apal.2020.102811","volume":"171","author":"Andrews U.","year":"2020","journal-title":"Ann. Pure Appl. Logic"},{"issue":"2","key":"S0218196723500339BIB005","doi-asserted-by":"crossref","first-page":"207","DOI":"10.2307\/1970103","volume":"70","author":"Boone W. W.","year":"1959","journal-title":"Ann. Math."},{"issue":"1","key":"S0218196723500339BIB006","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF01456932","volume":"71","author":"Dehn M.","year":"1911","journal-title":"Math. Ann."},{"issue":"3","key":"S0218196723500339BIB007","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1002\/malq.202000021","volume":"66","author":"Delle Rose V.","year":"2020","journal-title":"MLQ Math. Log. Q."},{"issue":"5","key":"S0218196723500339BIB008","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/s10469-021-09656-6","volume":"60","author":"Delle Rose V.","year":"2021","journal-title":"Algebra Logic"},{"issue":"2","key":"S0218196723500339BIB009","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1017\/jsl.2015.11","volume":"81","author":"Fokina E.","year":"2016","journal-title":"J. Symb. Logic"},{"issue":"1","key":"S0218196723500339BIB010","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1023\/A:1010521410739","volume":"67","author":"Gao S.","year":"2001","journal-title":"Studia Logica"},{"issue":"7","key":"S0218196723500339BIB011","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1016\/j.apal.2014.04.001","volume":"165","author":"Gavruskin A.","year":"2014","journal-title":"Ann. Pure Appl. Logic"},{"key":"S0218196723500339BIB012","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.tcs.2015.11.042","volume":"612","author":"Gavryushkin A.","year":"2016","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"S0218196723500339BIB014","doi-asserted-by":"crossref","first-page":"359","DOI":"10.3233\/COM-180101","volume":"8","author":"Harrison-Trainor M.","year":"2019","journal-title":"Computability"},{"issue":"5","key":"S0218196723500339BIB015","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/s10469-012-9203-8","volume":"51","author":"Hirschfeldt D. R.","year":"2012","journal-title":"Algebra Logic"},{"key":"S0218196723500339BIB016","doi-asserted-by":"crossref","first-page":"489","DOI":"10.2307\/2270912","volume":"34","author":"Jockusch C. G.","year":"1969","journal-title":"J. Symbolic Logic"},{"key":"S0218196723500339BIB017","doi-asserted-by":"crossref","first-page":"605","DOI":"10.2140\/pjm.1972.40.605","volume":"40","author":"Jockusch C. G.","year":"1972","journal-title":"Pacific J. Math."},{"issue":"6","key":"S0218196723500339BIB018","first-page":"771","volume":"26","author":"Kasymov N. K.","year":"1987","journal-title":"Algebra i Logika"},{"key":"S0218196723500339BIB019","first-page":"3","volume-title":"Vychisl. Sistemy","volume":"116","author":"Kasymov N. K.","year":"1986"},{"issue":"1","key":"S0218196723500339BIB020","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s10469-016-9373-x","volume":"55","author":"Kasymov N. K.","year":"2016","journal-title":"Algebra Logika"},{"key":"S0218196723500339BIB021","first-page":"56","volume-title":"Proc. Joint Meeting of the 23rd EACSL Annual Conf. Computer Science Logic and the 29th Annual ACM\/IEEE Symp. Logic in Computer Science","author":"Khoussainov B.","year":"2014"},{"key":"S0218196723500339BIB022","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-319-94418-0_1","volume-title":"Sailing Routes in the World of Computation, 14th Conf. Computability in Europe","volume":"10936","author":"Khoussainov B.","year":"2018"},{"issue":"3","key":"S0218196723500339BIB023","doi-asserted-by":"crossref","first-page":"1455","DOI":"10.1090\/S0002-9947-2013-05898-9","volume":"366","author":"Khoussainov B.","year":"2014","journal-title":"Trans. Amer. Math. Soc."},{"issue":"6","key":"S0218196723500339BIB024","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1007\/s00153-006-0013-3","volume":"45","author":"Khoussainov B.","year":"2006","journal-title":"Arch. Math. Logic"},{"key":"S0218196723500339BIB025","first-page":"172","volume":"9","author":"Litvinceva Z. K.","year":"1970","journal-title":"Algebra Logic"},{"key":"S0218196723500339BIB026","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1002\/malq.19660120125","volume":"12","author":"Martin D. A.","year":"1966","journal-title":"Z. Math. Logik Grundlagen Math."},{"issue":"11","key":"S0218196723500339BIB027","doi-asserted-by":"crossref","first-page":"2789","DOI":"10.1016\/j.jpaa.2011.03.019","volume":"215","author":"Myasnikov A.","year":"2011","journal-title":"J. Pure Appl. Algebra"},{"issue":"3","key":"S0218196723500339BIB028","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0960129516000335","volume":"28","author":"Nies A.","year":"2018","journal-title":"Math. Struct. Comput. Sci."},{"key":"S0218196723500339BIB029","first-page":"143","volume":"44","author":"Novikov P. S.","year":"1955","journal-title":"Trudy Mat. Inst. Steklov."},{"issue":"5","key":"S0218196723500339BIB030","doi-asserted-by":"crossref","first-page":"1617","DOI":"10.1090\/S0002-9939-2011-11000-1","volume":"140","author":"Miller J. S.","year":"2012","journal-title":"Proc. Amer. Math. Soc."},{"key":"S0218196723500339BIB031","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/978-1-4615-0755-0_14","volume-title":"Computability and Models","author":"Selivanov V.","year":"2003"},{"key":"S0218196723500339BIB032","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1002\/malq.19650110210","volume":"11","author":"Shepherdson J. C.","year":"1965","journal-title":"Z. Math. Logik Grundlagen Math."},{"key":"S0218196723500339BIB033","series-title":"Theory and Applications of Computability","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-31933-4","volume-title":"Turing Computability","author":"Soare R. I.","year":"2016"},{"key":"S0218196723500339BIB034","first-page":"71","volume-title":"Proc. Symp. Math. Theory of Automata","author":"Tennenbaum S.","year":"1963"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196723500339","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,17]],"date-time":"2023-07-17T07:02:53Z","timestamp":1689577373000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218196723500339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":33,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["10.1142\/S0218196723500339"],"URL":"https:\/\/doi.org\/10.1142\/s0218196723500339","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6]]}}}