{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,26]],"date-time":"2026-10-26T07:34:24Z","timestamp":1793000064176,"version":"4.5.0"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101097307"],"award-info":[{"award-number":["101097307"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010350","name":"Magdalen College, University of Oxford","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010350","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014013","name":"UK Research and Innovation","doi-asserted-by":"publisher","award":["EP\/X033813\/1"],"award-info":[{"award-number":["EP\/X033813\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We consider semigroup algorithmic problems in finitely generated metabelian groups. Our paper focuses on three decision problems introduced by Choffrut and Karhum\u00e4ki [ RAIRO Theor. Inform. Appl., 39 (2005), pp. 125\u2013131]: the identity problem (does a semigroup contain a neutral element?), the group problem (is a semigroup a group?),\u00a0and the inverse problem (does a semigroup contain the inverse of a generator?). We show that all three problems are decidable for finitely generated subsemigroups of finitely generated metabelian groups. In particular, we establish a correspondence between polynomial semirings and subsemigroups of metabelian groups using an interaction of graph theory, convex polytopes, algebraic geometry,\u00a0and number theory. Since the semigroup membership problem (does a semigroup contain a given element?) is known to be undecidable in finitely generated metabelian groups, our result advances the decidability characterization of semigroup algorithmic problems in metabelian groups.<\/jats:p>","DOI":"10.1137\/25m1763640","type":"journal-article","created":{"date-parts":[[2026,10,26]],"date-time":"2026-10-26T07:00:36Z","timestamp":1792998036000},"page":"977-1031","source":"Crossref","is-referenced-by-count":0,"title":["Semigroup Algorithmic Problems in Metabelian Groups"],"prefix":"10.1137","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-4349-082X","authenticated-orcid":true,"given":"Ruiwen","family":"Dong","sequence":"first","affiliation":[{"name":"Magdalen College, University of Oxford, OX1 4AU, United Kingdom."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,10,26]]},"reference":[{"key":"ref1","first-page":"533","volume":"103","author":"Adyan S. I.","year":"1955","journal-title":"Dokl. Akad. Nauk SSSR (N.S.)"},{"key":"ref2","series-title":"Springer Monographs in Mathematics 109","volume-title":"Convex Polyhedra","author":"Alexandrov A. D.","year":"2005"},{"key":"ref3","unstructured":"L. Babai, R. Beals, J.y. Cai, G. Ivanyos, and E. M. Luks, Multiplicative equations over commuting matrices, in SODA \u201996: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1996, pp. 498\u2013507."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700013987"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1994-1202419-X"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(85)90085-7"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/6838"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"R. Beals and L. Babai, Las Vegas algorithms for matrix groups, in Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, IEEE, New York, 1993, pp. 427\u2013436, https:\/\/doi.org\/10.1109\/SFCS.1993.366844.","DOI":"10.1109\/SFCS.1993.366844"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"P. C. Bell, M. Hirvensalo, and I. Potapov, The identity problem for matrix semigroups in \\({SL}_2(\\mathbb{Z})\\) is NP-complete, in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 187\u2013206, https:\/\/doi.org\/10.1137\/1.9781611974782.13.","DOI":"10.1137\/1.9781611974782.13"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054110007660"},{"key":"ref11","first-page":"25","volume":"1","author":"Berkesch C.","year":"2015","journal-title":"Commut. Algebra Noncommut. Algebraic Geom."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703425861"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2025.10.051"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"C. Bodart and R. Dong, The identity problem in virtually solvable matrix groups over algebraic numbers, in 40th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS 2025), ACM, New York, pp. 249\u2013261.","DOI":"10.1109\/LICS65433.2025.00026"},{"key":"ref15","series-title":"Leibniz International Proceedings in Informatics 168","first-page":"116:1","volume-title":"47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)","author":"Cadilhac M.","year":"2020"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2005007"},{"key":"ref17","unstructured":"T. Colcombet, J. Ouaknine, P. Semukhin, and J. Worrell, On reachability problems for low-dimensional matrix semigroups, in 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Leibniz International Proceedings in Informatics 132, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2019, pp. 44:1\u201344:15, https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2019.44."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0165-3_24"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2004.11.008"},{"key":"ref20","series-title":"Leibniz International Proceedings in Informatics 261","first-page":"124:1","volume-title":"50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)","author":"Dong R.","year":"2023"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"R. Dong, The identity problem in nilpotent groups of bounded class, in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2024, pp. 3919\u20133959, https:\/\/doi.org\/10.1137\/1.9781611977912.138.","DOI":"10.1137\/1.9781611977912.138"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"R. Dong, Semigroup algorithmic problems in metabelian groups, in STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, ACM, New York, 2024, pp. 884\u2013891, https:\/\/doi.org\/10.1145\/3618260.3649609.","DOI":"10.1145\/3618260.3649609"},{"key":"ref23","series-title":"Leibniz International Proceedings in Informatics 334","first-page":"154:1","volume-title":"52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)","author":"Dong R.","year":"2025"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00605-003-0051-4"},{"key":"ref25","series-title":"Graduate Texts in Mathematics 150","volume-title":"Commutative Algebra: With a View toward Algebraic Geometry","author":"Eisenbud D.","year":"2013"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-4.1.419"},{"key":"ref27","series-title":"Memoirs of the American Mathematical Society 54","volume-title":"Positive Polynomials and Product Type Actions of Compact Groups","author":"Handelman D.","year":"1985"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"E. Hrushovski, J. Ouaknine, A. Pouly, and J. Worrell, Polynomial invariants for affine programs, in LICS \u201918: Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science, ACM, New York, 2018, pp. 530\u2013539, https:\/\/doi.org\/10.1145\/3209108.3209142.","DOI":"10.1145\/3209108.3209142"},{"key":"ref29","first-page":"852","volume":"19","author":"Kharlampovich O. G.","year":"1981","journal-title":"Izv. Ross. Akad. Nauk Ser. Mat."},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196795000227"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/BF02220029"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"J. C. Lennox and D. J. Robinson, The Theory of Infinite Soluble Groups, Oxford University Press, Oxford,\u00a02004, https:\/\/doi.org\/10.1093\/acprof:oso\/9780198507284.001.0001.","DOI":"10.1093\/acprof:oso\/9780198507284.001.0001"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.014"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.2307\/1968892"},{"key":"ref35","first-page":"1089","volume":"78","author":"Markov A. A.","year":"1951","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"ref36","first-page":"241","volume":"36","author":"Mikhailova K. A.","year":"1966","journal-title":"Mat. Sb."},{"key":"ref37","volume-title":"Topology: A First Course","author":"Munkres J. R.","year":"1974"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"P. Narendran, Solving linear equations over polynomial semirings, in Proceedings 11th Annual IEEE Symposium on Logic in Computer Science, IEEE, New York, 1996, pp. 466\u2013472, https:\/\/doi.org\/10.1109\/LICS.1996.561463.","DOI":"10.1109\/LICS.1996.561463"},{"key":"ref39","first-page":"252","volume":"31","author":"Noskov G. A.","year":"1982","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"ref40","volume-title":"Trudy Matematicheskogo Instituta imeni V.A. Steklova 44","author":"Novikov P. S.","year":"1955"},{"key":"ref41","first-page":"293","volume":"20","author":"Roman\u2019kov V. A.","year":"2023","journal-title":"Sib. Elektron. Mat. Izv."},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/BF01462922"},{"key":"ref43","unstructured":"F.O. Schreyer, Die Berechnung von Syzygien mit dem verallgemeinerten Weierstra\u00dfschen Divisionssatz, Master\u2019s thesis, Fakult\u00e4t f\u00fcr Mathematik, Universit\u00e4t Hamburg, 1980."},{"key":"ref44","unstructured":"D. Shafrir, Bounded Generation of Submonoids of Heisenberg Groups, preprint, arXiv:2405.05939, 2024."},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1525\/9780520348097"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/25M1763640","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,26]],"date-time":"2026-10-26T07:00:51Z","timestamp":1792998051000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1763640"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,10,26]]},"references-count":45,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,10,31]]}},"alternative-id":["10.1137\/25M1763640"],"URL":"https:\/\/doi.org\/10.1137\/25m1763640","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,10,26]]}}}