{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T08:47:56Z","timestamp":1758617276615,"version":"3.44.0"},"reference-count":52,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:p> Motivated by a theorem of Groves and Wilton, we propose the study of the lattice of numberings of isomorphism classes of marked groups as a rigorous and comprehensive framework for the study of global decision problems for finitely generated groups. We establish the Rice and Rice\u2013Shapiro Theorems for recursive presentations, and establish similar results for co-recursive presentations. We give an algorithmic characterization of finitely presentable groups in terms of semi-decidability of two decision problems: the word problem and the marked quotient problem, which we introduce. We explain how this result can be used to define algorithmic generalizations of finite presentations. Finally, we discuss how the Adian\u2013Rabin Theorem provides incomplete answers in several respects. <\/jats:p>","DOI":"10.1142\/s0218196725500328","type":"journal-article","created":{"date-parts":[[2025,7,18]],"date-time":"2025-07-18T10:17:01Z","timestamp":1752833821000},"page":"1019-1053","source":"Crossref","is-referenced-by-count":0,"title":["Remarks and problems about algorithmic descriptions of groups"],"prefix":"10.1142","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-0395-3311","authenticated-orcid":false,"given":"Emmanuel","family":"Rauzy","sequence":"first","affiliation":[{"name":"Universit\u00e4t der Bundeswehr M\u00fcnchen, Institut f\u00fcr Theoretische Informatik, Mathematik und Operations Research &, Alexander von Humboldt Stiftung, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2025,7,31]]},"reference":[{"key":"S0218196725500328BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-8693(03)00268-0"},{"key":"S0218196725500328BIB003","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10572"},{"key":"S0218196725500328BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-019-00690-x"},{"key":"S0218196725500328BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/0040-9383(83)90044-7"},{"key":"S0218196725500328BIB006","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196708004871"},{"key":"S0218196725500328BIB007","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1948-0027263-2"},{"key":"S0218196725500328BIB008","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdp008"},{"key":"S0218196725500328BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2006.03.025"},{"issue":"223","key":"S0218196725500328BIB010","first-page":"402","volume":"16","author":"Banach S.","year":"1937","journal-title":"Ann. Soc. Pol. de Math"},{"key":"S0218196725500328BIB011","doi-asserted-by":"publisher","DOI":"10.4171\/ggd\/1"},{"key":"S0218196725500328BIB012","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10808"},{"key":"S0218196725500328BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-015-0578-8"},{"key":"S0218196725500328BIB014","first-page":"1","volume":"67","author":"Ceitin G. S.","year":"1967","journal-title":"Tr. Mat. Inst. Steklov"},{"key":"S0218196725500328BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773526"},{"key":"S0218196725500328BIB016","doi-asserted-by":"publisher","DOI":"10.1080\/00927872.2014.955579"},{"key":"S0218196725500328BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2006.02.012"},{"key":"S0218196725500328BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456932"},{"key":"S0218196725500328BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4668-8_8"},{"key":"S0218196725500328BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.exmath.2018.07.002"},{"key":"S0218196725500328BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/s10240-008-0014-3"},{"key":"S0218196725500328BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2008.06.007"},{"key":"S0218196725500328BIB024","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803757"},{"key":"S0218196725500328BIB025","doi-asserted-by":"publisher","DOI":"10.1201\/9781439865699"},{"key":"S0218196725500328BIB027","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-17.3.427"},{"key":"S0218196725500328BIB028","doi-asserted-by":"publisher","DOI":"10.4171\/ggd\/63"},{"key":"S0218196725500328BIB029","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196711006637"},{"key":"S0218196725500328BIB030","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_82"},{"key":"S0218196725500328BIB031","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9726-9"},{"key":"S0218196725500328BIB032","doi-asserted-by":"publisher","DOI":"10.1007\/s13373-017-0103-z"},{"key":"S0218196725500328BIB033","doi-asserted-by":"publisher","DOI":"10.1017\/S0004972700031014"},{"key":"S0218196725500328BIB034","doi-asserted-by":"publisher","DOI":"10.1007\/BF01234319"},{"key":"S0218196725500328BIB035","doi-asserted-by":"publisher","DOI":"10.1070\/IM1985v025n01ABEH001269"},{"key":"S0218196725500328BIB036","first-page":"77","volume":"16","author":"Maltsev A. I.","year":"1961","journal-title":"Uspehi Mat. Nauk"},{"key":"S0218196725500328BIB038","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/14.2.112"},{"key":"S0218196725500328BIB039","doi-asserted-by":"publisher","DOI":"10.2307\/2268172"},{"key":"S0218196725500328BIB040","doi-asserted-by":"publisher","DOI":"10.1017\/bsl.2014.32"},{"key":"S0218196725500328BIB041","doi-asserted-by":"publisher","DOI":"10.1070\/SM1968v004n02ABEH002788"},{"key":"S0218196725500328BIB042","doi-asserted-by":"publisher","DOI":"10.1515\/9781400881789"},{"key":"S0218196725500328BIB044","doi-asserted-by":"publisher","DOI":"10.4064\/fm-55-3-215-238"},{"key":"S0218196725500328BIB045","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71919-0"},{"key":"S0218196725500328BIB046","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2006.07.015"},{"key":"S0218196725500328BIB047","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7643-8412-8_8"},{"key":"S0218196725500328BIB048","doi-asserted-by":"publisher","DOI":"10.1017\/S1474748014000309"},{"key":"S0218196725500328BIB050","doi-asserted-by":"publisher","DOI":"10.1515\/jgth-2020-0029"},{"volume-title":"Theory of Recursive Functions and Effective Computability","year":"1987","author":"Rogers H.","key":"S0218196725500328BIB051"},{"key":"S0218196725500328BIB052","doi-asserted-by":"publisher","DOI":"10.1007\/s13373-011-0008-1"},{"key":"S0218196725500328BIB053","doi-asserted-by":"publisher","DOI":"10.1007\/s10240-001-8188-y"},{"key":"S0218196725500328BIB054","doi-asserted-by":"publisher","DOI":"10.2307\/2586596"},{"key":"S0218196725500328BIB055","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129516000190"},{"key":"S0218196725500328BIB056","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-008-0657-8"},{"key":"S0218196725500328BIB057","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90083-X"},{"key":"S0218196725500328BIB058","first-page":"773","volume":"103","author":"Uspensky V. A.","year":"1955","journal-title":"Doklady Akademii Nauk SSSR"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196725500328","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T07:43:00Z","timestamp":1758613380000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218196725500328"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,31]]},"references-count":52,"journal-issue":{"issue":"07","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["10.1142\/S0218196725500328"],"URL":"https:\/\/doi.org\/10.1142\/s0218196725500328","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"type":"print","value":"0218-1967"},{"type":"electronic","value":"1793-6500"}],"subject":[],"published":{"date-parts":[[2025,7,31]]}}}