{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T05:12:53Z","timestamp":1768972373226,"version":"3.49.0"},"reference-count":82,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,10,1]],"date-time":"2023-10-01T00:00:00Z","timestamp":1696118400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM SIGLOG News"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:p>\n            In this article we survey recent progress in the algorithmic theory of matrix semigroups. The main objective in this area of study is to construct algorithms that decide various properties of finitely generated subsemi-groups of an infinite group\n            <jats:italic>G<\/jats:italic>\n            , often represented as a matrix group. Such problems might not be decidable in general. In fact, they gave rise to some of the earliest undecidability results in algorithmic theory. However, the situation changes when the group\n            <jats:italic>G<\/jats:italic>\n            satisfies additional constraints. In this survey, we give an overview of the decidability and the complexity of several algorithmic problems in the cases where\n            <jats:italic>G<\/jats:italic>\n            is a low-dimensional matrix group, or a group with additional structures such as commutativity, nilpotency and solvability.\n          <\/jats:p>","DOI":"10.1145\/3636362.3636365","type":"journal-article","created":{"date-parts":[[2023,12,4]],"date-time":"2023-12-04T17:07:49Z","timestamp":1701709669000},"page":"3-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Recent Advances in Algorithmic Problems for Semigroups"],"prefix":"10.1145","volume":"10","author":[{"given":"Ruiwen","family":"Dong","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,4]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"533","article-title":"Algorithmic unsolvability of problems of recognition of certain properties of groups","volume":"103","author":"Adyan Sergei I.","year":"1955","unstructured":"Sergei I. Adyan . 1955 . Algorithmic unsolvability of problems of recognition of certain properties of groups . In Dokl. Akad. Nauk SSSR (N.S.) , Vol. 103. 533 -- 535 . Sergei I. Adyan. 1955. Algorithmic unsolvability of problems of recognition of certain properties of groups. In Dokl. Akad. Nauk SSSR (N.S.), Vol. 103. 533--535.","journal-title":"Dokl. Akad. Nauk SSSR (N.S.)"},{"key":"e_1_2_1_2_1","first-page":"122","article-title":"Coset intersection in moderately exponential time","volume":"88","author":"Babai L\u00e1szl\u00f3","year":"2010","unstructured":"L\u00e1szl\u00f3 Babai . 2010 . Coset intersection in moderately exponential time . Chicago J. Theoret. Comp. Sci 88 (2010), 122 -- 123 . L\u00e1szl\u00f3 Babai. 2010. Coset intersection in moderately exponential time. Chicago J. Theoret. Comp. Sci 88 (2010), 122--123.","journal-title":"Chicago J. Theoret. Comp. Sci"},{"key":"e_1_2_1_3_1","volume-title":"Luks","author":"Babai L\u00e1szl\u00f3","year":"1996","unstructured":"L\u00e1szl\u00f3 Babai , Robert Beals , Jin-yi Cai, G\u00e1bor Ivanyos , and Eugene M . Luks . 1996 . Multiplicative equations over commuting matrices. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. 498--507. L\u00e1szl\u00f3 Babai, Robert Beals, Jin-yi Cai, G\u00e1bor Ivanyos, and Eugene M. Luks. 1996. Multiplicative equations over commuting matrices. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. 498--507."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1112\/plms\/s2-3.1.24","article-title":"Alternants and continuous groups","volume":"2","author":"Baker Henry Frederick","year":"1905","unstructured":"Henry Frederick Baker . 1905 . Alternants and continuous groups . Proceedings of the London Mathematical Society 2 , 1(1905), 24 -- 47 . Henry Frederick Baker. 1905. Alternants and continuous groups. Proceedings of the London Mathematical Society 2, 1(1905), 24--47.","journal-title":"Proceedings of the London Mathematical Society"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1017\/S1446788700013987","article-title":"Subgroups of finitely presented metabelian groups","volume":"16","author":"Baumslag Gilbert","year":"1973","unstructured":"Gilbert Baumslag . 1973 . Subgroups of finitely presented metabelian groups . Journal of the Australian Mathematical Society 16 , 1 (1973), 98 -- 110 . Gilbert Baumslag. 1973. Subgroups of finitely presented metabelian groups. Journal of the Australian Mathematical Society 16, 1 (1973), 98--110.","journal-title":"Journal of the Australian Mathematical Society"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1090\/S0002-9947-1994-1202419-X","article-title":"The algorithmic theory of finitely generated metabelian groups","volume":"344","author":"Baumslag Gilbert","year":"1994","unstructured":"Gilbert Baumslag , Frank B. Cannonito , and Derek J.S. Robinson . 1994 . The algorithmic theory of finitely generated metabelian groups . Trans. Amer. Math. Soc. 344 , 2 (1994), 629 -- 648 . Gilbert Baumslag, Frank B. Cannonito, and Derek J.S. Robinson. 1994. The algorithmic theory of finitely generated metabelian groups. Trans. Amer. Math. Soc. 344, 2 (1994), 629--648.","journal-title":"Trans. Amer. Math. Soc."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"657","DOI":"10.4171\/ggd\/99","article-title":"Subgroups of free metabelian groups","volume":"4","author":"Baumslag Gilbert","year":"2010","unstructured":"Gilbert Baumslag , Charles F. Miller III, and Gretchen Ostheimer . 2010 . Subgroups of free metabelian groups . Groups, Geometry, and Dynamics 4 , 4 (2010), 657 -- 679 . Gilbert Baumslag, Charles F. Miller III, and Gretchen Ostheimer. 2010. Subgroups of free metabelian groups. Groups, Geometry, and Dynamics 4, 4 (2010), 657--679.","journal-title":"Groups, Geometry, and Dynamics"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"G. Baumslag and Y. Roitberg. 1982. Groups with free 2-generator subsemigroups. In Semigroup forum Vol. 25. Springer 135--143.  G. Baumslag and Y. Roitberg. 1982. Groups with free 2-generator subsemigroups. In Semigroup forum Vol. 25. Springer 135--143.","DOI":"10.1007\/BF02573593"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. IEEE, 427--436","author":"Beals Robert","year":"1993","unstructured":"Robert Beals and L\u00e1szl\u00f3 Babai . 1993 . Las Vegas algorithms for matrix groups . In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. IEEE, 427--436 . Robert Beals and L\u00e1szl\u00f3 Babai. 1993. Las Vegas algorithms for matrix groups. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. IEEE, 427--436."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.06.004"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039699"},{"key":"e_1_2_1_12_1","unstructured":"Paul C. Bell Mika Hirvensalo and Igor Potapov. 2023. Private Communication. (2023).  Paul C. Bell Mika Hirvensalo and Igor Potapov. 2023. Private Communication. (2023)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054110007660"},{"key":"e_1_2_1_14_1","first-page":"1188","article-title":"Parties rationnelles du groupe libre. CR","volume":"269","author":"Benois Mich\u00e8le","year":"1969","unstructured":"Mich\u00e8le Benois . 1969 . Parties rationnelles du groupe libre. CR Acad. Sci. Paris, S\u00e9r. A 269 (1969), 1188 -- 1190 . Mich\u00e8le Benois. 1969. Parties rationnelles du groupe libre. CR Acad. Sci. Paris, S\u00e9r. A 269 (1969), 1188--1190.","journal-title":"Acad. Sci. Paris, S\u00e9r. A"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703425861"},{"key":"e_1_2_1_16_1","volume-title":"Norway","author":"Bruinier Jan Hendrik","year":"2008","unstructured":"Jan Hendrik Bruinier , Gerard van der Geer , G\u00fcnter Harder , and Don Zagier . 2008. Elliptic modular forms and their applications. The 1-2-3 of modular forms: Lectures at a summer school in Nordfjordeid , Norway ( 2008 ), 1--103. Jan Hendrik Bruinier, Gerard van der Geer, G\u00fcnter Harder, and Don Zagier. 2008. Elliptic modular forms and their applications. The 1-2-3 of modular forms: Lectures at a summer school in Nordfjordeid, Norway (2008), 1--103."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1017\/etds.2015.45","article-title":"Classifying orbits of the affine group over the integers","volume":"37","author":"Cabrer Leonardo Manuel","year":"2017","unstructured":"Leonardo Manuel Cabrer and Daniele Mundici . 2017 . Classifying orbits of the affine group over the integers . Ergodic Theory and Dynamical Systems 37 , 2 (2017), 440 -- 453 . Leonardo Manuel Cabrer and Daniele Mundici. 2017. Classifying orbits of the affine group over the integers. Ergodic Theory and Dynamical Systems 37, 2 (2017), 440--453.","journal-title":"Ergodic Theory and Dynamical Systems"},{"key":"e_1_2_1_18_1","volume-title":"47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 (LIPIcs)","volume":"168","author":"Cadilhac Micha\u00ebl","year":"2020","unstructured":"Micha\u00ebl Cadilhac , Dmitry Chistikov , and Georg Zetzsche . 2020 . Rational Subsets of Baumslag-Solitar Groups. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 (LIPIcs) , Vol. 168 . 116:1--116:16. Micha\u00ebl Cadilhac, Dmitry Chistikov, and Georg Zetzsche. 2020. Rational Subsets of Baumslag-Solitar Groups. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 (LIPIcs), Vol. 168. 116:1--116:16."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1112\/plms\/s1-29.1.14","article-title":"On a law of combination of operators (second paper)","volume":"1","author":"Campbell John Edward","year":"1897","unstructured":"John Edward Campbell . 1897 . On a law of combination of operators (second paper) . Proceedings of the London Mathematical Society 1 , 1 (1897), 14 -- 32 . John Edward Campbell. 1897. On a law of combination of operators (second paper). Proceedings of the London Mathematical Society 1, 1 (1897), 14--32.","journal-title":"Proceedings of the London Mathematical Society"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196799000199"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2012010"},{"key":"e_1_2_1_22_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Chistikov Dmitry","unstructured":"Dmitry Chistikov and Christoph Haase . 2016. The taming of the semi-linear set . In International Colloquium on Automata, Languages, and Programming , Vol. 55 . Schloss Dagstuhl . Dmitry Chistikov and Christoph Haase. 2016. The taming of the semi-linear set. In International Colloquium on Automata, Languages, and Programming, Vol. 55. Schloss Dagstuhl."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2005007"},{"key":"e_1_2_1_24_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 (LIPIcs)","volume":"132","author":"Colcombet Thomas","year":"2019","unstructured":"Thomas Colcombet , Jo\u00ebl Ouaknine , Pavel Semukhin , and James Worrell . 2019 . On Reachability Problems for Low-Dimensional Matrix Semigroups. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 (LIPIcs) , Vol. 132 . 44:1--44:15. Thomas Colcombet, Jo\u00ebl Ouaknine, Pavel Semukhin, and James Worrell. 2019. On Reachability Problems for Low-Dimensional Matrix Semigroups. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 (LIPIcs), Vol. 132. 44:1--44:15."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2004.11.008"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373207.3404038"},{"key":"e_1_2_1_28_1","volume-title":"The Identity Problem in nilpotent groups of bounded class. arXiv preprint arXiv:2208.02164","author":"Dong Ruiwen","year":"2022","unstructured":"Ruiwen Dong . 2022. The Identity Problem in nilpotent groups of bounded class. arXiv preprint arXiv:2208.02164 ( 2022 ). Ruiwen Dong. 2022. The Identity Problem in nilpotent groups of bounded class. arXiv preprint arXiv:2208.02164 (2022)."},{"key":"e_1_2_1_29_1","volume-title":"50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 (LIPIcs)","volume":"261","author":"Dong Ruiwen","year":"2023","unstructured":"Ruiwen Dong . 2023 a. The Identity Problem in Z &int; Z Is Decidable. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 (LIPIcs) , Vol. 261 . 124:1--124:20. Ruiwen Dong. 2023a. The Identity Problem in Z &int; Z Is Decidable. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 (LIPIcs), Vol. 261. 124:1--124:20."},{"key":"e_1_2_1_30_1","volume-title":"2023 38th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 1--13","author":"Dong Ruiwen","year":"2023","unstructured":"Ruiwen Dong . 2023 b. The Identity Problem in the special affine group of Z2 . In 2023 38th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 1--13 . Ruiwen Dong. 2023b. The Identity Problem in the special affine group of Z2. In 2023 38th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 1--13."},{"key":"e_1_2_1_31_1","volume-title":"Semigroup algorithmic problems in metabelian groups. arXiv preprint arXiv:2304.12893","author":"Dong Ruiwen","year":"2023","unstructured":"Ruiwen Dong . 2023c. Semigroup algorithmic problems in metabelian groups. arXiv preprint arXiv:2304.12893 ( 2023 ). Ruiwen Dong. 2023c. Semigroup algorithmic problems in metabelian groups. arXiv preprint arXiv:2304.12893 (2023)."},{"key":"e_1_2_1_32_1","volume-title":"Semigroup Intersection Problems in the Heisenberg Groups. In 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023 (LIPIcs)","volume":"254","author":"Dong Ruiwen","year":"2023","unstructured":"Ruiwen Dong . 2023 d. Semigroup Intersection Problems in the Heisenberg Groups. In 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023 (LIPIcs) , Vol. 254 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 25:1--25:18. Ruiwen Dong. 2023d. Semigroup Intersection Problems in the Heisenberg Groups. In 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023 (LIPIcs), Vol. 254. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 25:1--25:18."},{"key":"e_1_2_1_33_1","volume-title":"Geometric group theory","author":"Dru\u0163u Cornelia","unstructured":"Cornelia Dru\u0163u and Michael Kapovich . 2018. Geometric group theory . Vol. 63 . American Mathematical Soc . Cornelia Dru\u0163u and Michael Kapovich. 2018. Geometric group theory. Vol. 63. American Mathematical Soc."},{"key":"e_1_2_1_34_1","volume-title":"2020 IEEE 23rd International Conference on Information Fusion (FUSION). IEEE, 1--8.","author":"Giefer Lino Antoni","year":"2020","unstructured":"Lino Antoni Giefer , Joachim Clemens , and Kerstin Schill . 2020 . Extended object tracking on the affine group Aff(2) . In 2020 IEEE 23rd International Conference on Information Fusion (FUSION). IEEE, 1--8. Lino Antoni Giefer, Joachim Clemens, and Kerstin Schill. 2020. Extended object tracking on the affine group Aff(2). In 2020 IEEE 23rd International Conference on Information Fusion (FUSION). IEEE, 1--8."},{"key":"e_1_2_1_35_1","first-page":"65","article-title":"Finitely presented centre-by-metabelian groups","volume":"2","author":"James Groves John Richard","year":"1978","unstructured":"John Richard James Groves . 1978 . Finitely presented centre-by-metabelian groups . Journal of the London Mathematical Society 2 , 1 (1978), 65 -- 69 . John Richard James Groves. 1978. Finitely presented centre-by-metabelian groups. Journal of the London Mathematical Society 2, 1 (1978), 65--69.","journal-title":"Journal of the London Mathematical Society"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.2307\/1971092"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the London Mathematical Society s3-4, 1 (01","author":"Hall P.","year":"1954","unstructured":"P. Hall . 1954 . Finiteness Conditions for Soluble Groups . Proceedings of the London Mathematical Society s3-4, 1 (01 1954), 419--436. P. Hall. 1954. Finiteness Conditions for Soluble Groups. Proceedings of the London Mathematical Society s3-4, 1 (01 1954), 419--436."},{"key":"e_1_2_1_38_1","first-page":"19","article-title":"Die symbolische Exponentialformel in der Gruppentheorie. Berichte \u00fcber die Verhandlungen der K\u00f6niglich-S\u00e4chsischen Gesellschaft der Wissenschaften zu Leipzig","volume":"58","author":"Hausdorff Felix","year":"1906","unstructured":"Felix Hausdorff . 1906 . Die symbolische Exponentialformel in der Gruppentheorie. Berichte \u00fcber die Verhandlungen der K\u00f6niglich-S\u00e4chsischen Gesellschaft der Wissenschaften zu Leipzig , Mathematisch-Physische Klasse 58 (1906), 19 -- 48 . Felix Hausdorff. 1906. Die symbolische Exponentialformel in der Gruppentheorie. Berichte \u00fcber die Verhandlungen der K\u00f6niglich-S\u00e4chsischen Gesellschaft der Wissenschaften zu Leipzig, Mathematisch-Physische Klasse 58 (1906), 19--48.","journal-title":"Mathematisch-Physische Klasse"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1090\/S0273-0979-1980-14825-9","article-title":"On the role of the Heisenberg group in harmonic analysis","volume":"3","author":"Howe Roger","year":"1980","unstructured":"Roger Howe . 1980 . On the role of the Heisenberg group in harmonic analysis . Bulletin (New Series) of the American Mathematical Society 3 , 2 (1980), 821 -- 843 . Roger Howe. 1980. On the role of the Heisenberg group in harmonic analysis. Bulletin (New Series) of the American Mathematical Society 3, 2 (1980), 821--843.","journal-title":"Bulletin (New Series) of the American Mathematical Society"},{"key":"e_1_2_1_40_1","volume-title":"On the Intersection of Finitely Generated Free Groups. Journal of the London Mathematical Society s1-29, 4 (10","author":"Howson A. G.","year":"1954","unstructured":"A. G. Howson . 1954. On the Intersection of Finitely Generated Free Groups. Journal of the London Mathematical Society s1-29, 4 (10 1954 ), 428--434. A. G. Howson. 1954. On the Intersection of Finitely Generated Free Groups. Journal of the London Mathematical Society s1-29, 4 (10 1954), 428--434."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209142"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.2001.9033"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021819670500213X"},{"key":"e_1_2_1_44_1","first-page":"852","article-title":"A finitely presented solvable group with unsolvable word problem","volume":"45","author":"Kharlampovich Ol'ga Georgievna","year":"1981","unstructured":"Ol'ga Georgievna Kharlampovich . 1981 . A finitely presented solvable group with unsolvable word problem . Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya 45 , 4 (1981), 852 -- 873 . Ol'ga Georgievna Kharlampovich. 1981. A finitely presented solvable group with unsolvable word problem. Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya 45, 4 (1981), 852--873.","journal-title":"Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya"},{"key":"e_1_2_1_45_1","volume-title":"Lectures on the orbit method","author":"Kirillov Aleksandr Aleksandrovich","unstructured":"Aleksandr Aleksandrovich Kirillov . 2004. Lectures on the orbit method . Vol. 64 . American Mathematical Soc . Aleksandr Aleksandrovich Kirillov. 2004. Lectures on the orbit method. Vol. 64. American Mathematical Soc."},{"key":"e_1_2_1_46_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 (LIPIcs)","volume":"107","author":"Ko Sang-Ki","year":"2018","unstructured":"Sang-Ki Ko , Reino Niskanen , and Igor Potapov . 2018 . On the identity problem for the Special Linear Group and the Heisenberg Group. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 (LIPIcs) , Vol. 107 . 132:1--132:15. Sang-Ki Ko, Reino Niskanen, and Igor Potapov. 2018. On the identity problem for the Special Linear Group and the Heisenberg Group. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 (LIPIcs), Vol. 107. 132:1--132:15."},{"key":"e_1_2_1_47_1","first-page":"138","article-title":"Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups","volume":"677","author":"K\u00f6nig Daniel","year":"2016","unstructured":"Daniel K\u00f6nig , Markus Lohrey , and Georg Zetzsche . 2016 . Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups . Algebra and Computer Science 677 (2016), 138 -- 153 . Daniel K\u00f6nig, Markus Lohrey, and Georg Zetzsche. 2016. Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups. Algebra and Computer Science 677 (2016), 138--153.","journal-title":"Algebra and Computer Science"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1007\/BF02220029","article-title":"Solvability of the problem of occurrence in finitely generated soluble groups of matrices over the field of algebraic numbers","volume":"7","author":"Kopytov V. M.","year":"1968","unstructured":"V. M. Kopytov . 1968 . Solvability of the problem of occurrence in finitely generated soluble groups of matrices over the field of algebraic numbers . Algebra and Logic 7 , 6 (1968), 388 -- 393 . V. M. Kopytov. 1968. Solvability of the problem of occurrence in finitely generated soluble groups of matrices over the field of algebraic numbers. Algebra and Logic 7, 6 (1968), 388--393.","journal-title":"Algebra and Logic"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0188316-1"},{"key":"e_1_2_1_50_1","volume-title":"Mathematical Methods in Computer Science","author":"Krovi Hari","unstructured":"Hari Krovi and Martin R\u00f6tteler . 2008. An efficient quantum algorithm for the hidden subgroup problem over Weyl-Heisenberg groups . In Mathematical Methods in Computer Science . Springer , 70--88. Hari Krovi and Martin R\u00f6tteler. 2008. An efficient quantum algorithm for the hidden subgroup problem over Weyl-Heisenberg groups. In Mathematical Methods in Computer Science. Springer, 70--88."},{"key":"e_1_2_1_51_1","volume-title":"Groups St Andrews","author":"Lohrey Markus","unstructured":"Markus Lohrey . 2013. The rational subset membership problem for groups: a survey . In Groups St Andrews , Vol. 422 . Cambridge University Press , 368--389. Markus Lohrey. 2013. The rational subset membership problem for groups: a survey. In Groups St Andrews, Vol. 422. Cambridge University Press, 368--389."},{"key":"e_1_2_1_52_1","volume-title":"Subgroup membership in GL(2,Z). Theory of Computing Systems","author":"Lohrey Markus","year":"2023","unstructured":"Markus Lohrey . 2023. Subgroup membership in GL(2,Z). Theory of Computing Systems ( 2023 ), 1--26. Markus Lohrey. 2023. Subgroup membership in GL(2,Z). Theory of Computing Systems (2023), 1--26."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.014"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1142\/S021819671950019X","article-title":"Low-complexity computations for nilpotent subgroup problems","volume":"29","author":"Macdonald Jeremy","year":"2019","unstructured":"Jeremy Macdonald , Alexei Miasnikov , and Denis Ovchinnikov . 2019 . Low-complexity computations for nilpotent subgroup problems . International Journal of Algebra and Computation 29 , 04 (2019), 639 -- 661 . Jeremy Macdonald, Alexei Miasnikov, and Denis Ovchinnikov. 2019. Low-complexity computations for nilpotent subgroup problems. International Journal of Algebra and Computation 29, 04 (2019), 639--661.","journal-title":"International Journal of Algebra and Computation"},{"key":"e_1_2_1_55_1","volume-title":"On a theorem for Marshall Hall. Annals of Mathematics","author":"Magnus Wilhelm","year":"1939","unstructured":"Wilhelm Magnus . 1939. On a theorem for Marshall Hall. Annals of Mathematics ( 1939 ), 764--768. Wilhelm Magnus. 1939. On a theorem for Marshall Hall. Annals of Mathematics (1939), 764--768."},{"key":"e_1_2_1_56_1","first-page":"107","article-title":"Nilpotent semigroups","volume":"4","author":"Mal'cev A. I.","year":"1953","unstructured":"A. I. Mal'cev . 1953 . Nilpotent semigroups . In Ivanov. Gos Ped. Inst. Ucen Zap. Fiz.-Mat. Nauki , Vol. 4. 107 -- 111 . A. I. Mal'cev. 1953. Nilpotent semigroups. In Ivanov. Gos Ped. Inst. Ucen Zap. Fiz.-Mat. Nauki, Vol. 4. 107--111.","journal-title":"Ivanov. Gos Ped. Inst. Ucen Zap. Fiz.-Mat. Nauki"},{"key":"e_1_2_1_57_1","first-page":"539","article-title":"On certain insoluble problems concerning matrices","volume":"57","author":"Markov A.","year":"1947","unstructured":"A. Markov . 1947 . On certain insoluble problems concerning matrices . Doklady Akad. Nauk SSSR 57 , 6 (1947), 539 -- 542 . A. Markov. 1947. On certain insoluble problems concerning matrices. Doklady Akad. Nauk SSSR 57, 6 (1947), 539--542.","journal-title":"Doklady Akad. Nauk SSSR"},{"key":"e_1_2_1_58_1","first-page":"279","article-title":"The Diophantineness of enumerable sets","volume":"191","author":"Matiyasevich Yuri Vladimirovich","year":"1970","unstructured":"Yuri Vladimirovich Matiyasevich . 1970 . The Diophantineness of enumerable sets . Doklady Akademii Nauk SSSR 191 , 2 (1970), 279 -- 282 . Yuri Vladimirovich Matiyasevich. 1970. The Diophantineness of enumerable sets. Doklady Akademii Nauk SSSR 191, 2 (1970), 279--282.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_2_1_59_1","first-page":"241","article-title":"The occurrence problem for direct products of groups","volume":"112","author":"Mikhailova K. A.","year":"1966","unstructured":"K. A. Mikhailova . 1966 . The occurrence problem for direct products of groups . Matematicheskii Sbornik 112 , 2 (1966), 241 -- 251 . K. A. Mikhailova. 1966. The occurrence problem for direct products of groups. Matematicheskii Sbornik 112, 2 (1966), 241--251.","journal-title":"Matematicheskii Sbornik"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/1095587"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831300062X"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2014-02880-9"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457956"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1255632506"},{"key":"e_1_2_1_65_1","volume-title":"On the algorithmic unsolvability of the word problem in group theory. Trudy Matematicheskogo Instituta imeni VA Steklova 44","author":"Novikov Petr Sergeevich","year":"1955","unstructured":"Petr Sergeevich Novikov . 1955. On the algorithmic unsolvability of the word problem in group theory. Trudy Matematicheskogo Instituta imeni VA Steklova 44 ( 1955 ), 3--143. Petr Sergeevich Novikov. 1955. On the algorithmic unsolvability of the word problem in group theory. Trudy Matematicheskogo Instituta imeni VA Steklova 44 (1955), 3--143."},{"key":"e_1_2_1_66_1","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0022-4049(95)00104-5","article-title":"Generalised Tits alternative for linear semigroups","volume":"103","author":"Okni\u0144ski J.","year":"1995","unstructured":"J. Okni\u0144ski and A. Salwa . 1995 . Generalised Tits alternative for linear semigroups . Journal of Pure and Applied Algebra 103 , 2 (1995), 211 -- 220 . J. Okni\u0144ski and A. Salwa. 1995. Generalised Tits alternative for linear semigroups. Journal of Pure and Applied Algebra 103, 2 (1995), 211--220.","journal-title":"Journal of Pure and Applied Algebra"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634101"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766189.2766191"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1970491105"},{"key":"e_1_2_1_70_1","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1017\/S0143385703000531","article-title":"Stable mixing for cat maps and quasi-morphisms of the modular group","volume":"24","author":"Polterovich Leonid","year":"2004","unstructured":"Leonid Polterovich and Zeev Rudnick . 2004 . Stable mixing for cat maps and quasi-morphisms of the modular group . Ergodic Theory and Dynamical Systems 24 , 2 (2004), 609 -- 619 . Leonid Polterovich and Zeev Rudnick. 2004. Stable mixing for cat maps and quasi-morphisms of the modular group. Ergodic Theory and Dynamical Systems 24, 2 (2004), 609--619.","journal-title":"Ergodic Theory and Dynamical Systems"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08555-9"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039698"},{"key":"e_1_2_1_73_1","volume-title":"42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 (LIPIcs)","volume":"83","author":"Potapov Igor","year":"2017","unstructured":"Igor Potapov and Pavel Semukhin . 2017 b. Membership Problem in GL(2, Z) Extended by Singular Matrices . In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 (LIPIcs) , Vol. 83 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 44:1--44:13. Igor Potapov and Pavel Semukhin. 2017b. Membership Problem in GL(2, Z) Extended by Singular Matrices. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 (LIPIcs), Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 44:1--44:13."},{"key":"e_1_2_1_74_1","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.jcss.2018.09.003","article-title":"Vector and scalar reachability problems in SL2(Z)","volume":"100","author":"Potapov Igor","year":"2019","unstructured":"Igor Potapov and Pavel Semukhin . 2019 . Vector and scalar reachability problems in SL2(Z) . J. Comput. System Sci. 100 (2019), 30 -- 43 . Igor Potapov and Pavel Semukhin. 2019. Vector and scalar reachability problems in SL2(Z). J. Comput. System Sci. 100 (2019), 30--43.","journal-title":"J. Comput. System Sci."},{"key":"e_1_2_1_75_1","volume-title":"Affine extensions of integer vector addition systems with states. Logical Methods in Computer Science 17","author":"Raskin Mikhail","year":"2021","unstructured":"Mikhail Raskin , Filip Mazowiecki , Christoph Haase , and Michael Blondin . 2021. Affine extensions of integer vector addition systems with states. Logical Methods in Computer Science 17 ( 2021 ). Mikhail Raskin, Filip Mazowiecki, Christoph Haase, and Michael Blondin. 2021. Affine extensions of integer vector addition systems with states. Logical Methods in Computer Science 17 (2021)."},{"key":"e_1_2_1_76_1","volume-title":"Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the Heisenberg group. arXiv preprint arXiv:2209.14786","author":"Roman'kov Vitaly","year":"2022","unstructured":"Vitaly Roman'kov . 2022. Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the Heisenberg group. arXiv preprint arXiv:2209.14786 ( 2022 ). Vitaly Roman'kov. 2022. Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the Heisenberg group. arXiv preprint arXiv:2209.14786 (2022)."},{"key":"e_1_2_1_77_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01462922","article-title":"Some algorithmic problems for solvable groups","volume":"13","author":"Romanovskii N. S.","year":"1974","unstructured":"N. S. Romanovskii . 1974 . Some algorithmic problems for solvable groups . Algebra and Logic 13 , 1 (1974), 13 -- 16 . N. S. Romanovskii. 1974. Some algorithmic problems for solvable groups. Algebra and Logic 13, 1 (1974), 13--16.","journal-title":"Algebra and Logic"},{"key":"e_1_2_1_78_1","volume-title":"Z). MathOverflow.","author":"R\u00fcping Henrik","year":"2010","unstructured":"Henrik R\u00fcping . 2010. The free group F2 has index 12 in SL(2 , Z). MathOverflow. ( 2010 ). https:\/\/mathoverflow.net\/q\/43740 (version: 2010-10-27). Username : HenrikR\u00fcping . Henrik R\u00fcping. 2010. The free group F2 has index 12 in SL(2, Z). MathOverflow. (2010). https:\/\/mathoverflow.net\/q\/43740 (version: 2010-10-27). Username: HenrikR\u00fcping."},{"key":"e_1_2_1_79_1","volume-title":"Einige S\u00e4tze \u00fcber gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf Diophantische Gleichungen. Acad","author":"Skolem T.","year":"1933","unstructured":"T. Skolem . 1933. Einige S\u00e4tze \u00fcber gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf Diophantische Gleichungen. Acad . Oslo, Mat . Naturv. Klasse 6 ( 1933 ). T. Skolem. 1933. Einige S\u00e4tze \u00fcber gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf Diophantische Gleichungen. Acad. Oslo, Mat. Naturv. Klasse 6 (1933)."},{"key":"e_1_2_1_80_1","unstructured":"Matti Soittola. 1975. On DOL Synthesis Problem. In Automata Languages Development. 313--321.  Matti Soittola. 1975. On DOL Synthesis Problem. In Automata Languages Development. 313--321."},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(72)90058-0"},{"key":"e_1_2_1_82_1","volume-title":"The theory of groups and quantum mechanics","author":"Weyl Hermann","unstructured":"Hermann Weyl . 1950. The theory of groups and quantum mechanics . Courier Corporation . Hermann Weyl. 1950. The theory of groups and quantum mechanics. Courier Corporation."},{"key":"e_1_2_1_83_1","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1090\/S0002-9939-1963-0145005-0","article-title":"The affine group of a Lie group","volume":"14","author":"Wolf Joseph A.","year":"1963","unstructured":"Joseph A. Wolf . 1963 . The affine group of a Lie group . In Proc. Amer. Math. Soc. , Vol. 14. 352 -- 353 . Joseph A. Wolf. 1963. The affine group of a Lie group. In Proc. Amer. Math. Soc., Vol. 14. 352--353.","journal-title":"Proc. Amer. Math. Soc."}],"container-title":["ACM SIGLOG News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3636362.3636365","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3636362.3636365","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:35:41Z","timestamp":1750178141000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3636362.3636365"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10]]},"references-count":82,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["10.1145\/3636362.3636365"],"URL":"https:\/\/doi.org\/10.1145\/3636362.3636365","relation":{},"ISSN":["2372-3491"],"issn-type":[{"value":"2372-3491","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10]]},"assertion":[{"value":"2023-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}