{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T01:02:18Z","timestamp":1767920538534,"version":"3.49.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-22-CE48-0005"],"award-info":[{"award-number":["ANR-22-CE48-0005"]}],"id":[{"id":"10.13039\/501100001665","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"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ARTIST 101002685"],"award-info":[{"award-number":["ARTIST 101002685"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Research Council","award":["MSCA COFUND 101034440"],"award-info":[{"award-number":["MSCA COFUND 101034440"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,1,8]]},"abstract":"<jats:p>Computational problems concerning the orbit of a point under the action of a matrix group occur throughout computer science, including in program analysis, complexity theory, quantum computation, and automata theory. In many cases the focus extends beyond orbits proper to orbit closures under a suitable topology. Typically one starts from a group and a set of points and asks questions about the orbit closure of the set under the action of the group, e.g., whether two given orbit closures intersect.<\/jats:p>\n                  <jats:p>\n                    In this paper we consider a collection of what we call determination problems concerning matrix groups and orbit closures. These problems begin with a given variety and seek to understand whether and how it arises either as an algebraic matrix group or as an orbit closure. The how question asks whether the underlying group is\n                    <jats:italic toggle=\"yes\">s<\/jats:italic>\n                    -generated, meaning it is topologically generated by\u00a0\n                    <jats:italic toggle=\"yes\">s<\/jats:italic>\n                    matrices for a given number\u00a0\n                    <jats:italic toggle=\"yes\">s<\/jats:italic>\n                    . Among other applications, problems of this type have recently been studied in the context of synthesising loops subject to certain specified invariants on program variables.\n                  <\/jats:p>\n                  <jats:p>\n                    Our main result is a polynomial-space procedure that inputs a variety and a number\u00a0\n                    <jats:italic toggle=\"yes\">s<\/jats:italic>\n                    and determines whether the given variety arises as an orbit closure of a point under an\n                    <jats:italic toggle=\"yes\">s<\/jats:italic>\n                    -generated commutative algebraic matrix group. The main tools in our approach are structural properties of commutative algebraic matrix groups and module theory. We leave open the question of determining whether a variety is an orbit closure of a point under an\n                    <jats:italic toggle=\"yes\">s<\/jats:italic>\n                    -generated algebraic matrix group (without the requirement of commutativity).\n                  <\/jats:p>","DOI":"10.1145\/3776698","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T18:59:43Z","timestamp":1767898783000},"page":"1615-1640","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Determination Problems for Orbit Closures and Matrix Groups"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6228-9071","authenticated-orcid":false,"given":"Rida Ait","family":"El Manssour","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7661-7061","authenticated-orcid":false,"given":"George","family":"Kenison","sequence":"additional","affiliation":[{"name":"Liverpool John Moores University, Liverpool, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7779-2339","authenticated-orcid":false,"given":"Mahsa","family":"Shirmohammadi","sequence":"additional","affiliation":[{"name":"CNRS, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5758-0657","authenticated-orcid":false,"given":"Anton","family":"Varonka","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8151-2443","authenticated-orcid":false,"given":"James","family":"Worrell","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3704862"},{"key":"e_1_2_1_2_1","unstructured":"Rida Ait El Manssour George Kenison Mahsa Shirmohammadi Anton Varonka and James Worrell. 2025. Determination Problems for Orbit Closures and Matrix Groups. 2407.04626. arxiv:2407.04626"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Babai L.","year":"1996","unstructured":"L. Babai, R. Beals, J.-Y. Cai, G. Ivanyos, and E. M. Luks. 1996. Multiplicative Equations over Commuting Matrices. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 28-30 January 1996, Atlanta, Georgia.. 498-507."},{"key":"e_1_2_1_4_1","volume-title":"Algorithms in real algebraic geometry","author":"Basu Saugata","unstructured":"Saugata Basu, Richard Pollack, and Marie-Fran\u00e7oise Roy. 2006. Algorithms in real algebraic geometry. Springer-Verlag, Berlin, Algorithms and Computation in Mathematics, Vol. 10. x+662."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235813"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.152"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511542879"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0941-6"},{"key":"e_1_2_1_9_1","unstructured":"Peter B\u00fcrgisser. 2024. Completeness classes in algebraic complexity theory."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.32"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/090765328"},{"key":"e_1_2_1_12_1","volume-title":"International Symposium on Mathematical Foundations of Computer Science. 17-31","author":"Chistov Alexander L","year":"1984","unstructured":"Alexander L Chistov and D Yu Grigor\u2019Ev. 1984. Complexity of quantifier elimination in the theory of algebraically closed fields. Springer, In International Symposium on Mathematical Foundations of Computer Science. 17-31."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Thierry Combot. 2025. Computing linear relations between polynomial roots.","DOI":"10.1090\/mcom\/4081"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16721-3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632867"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2004.11.008"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2140\/ant.2020.14.2791"},{"key":"e_1_2_1_18_1","volume-title":"Forbes and Amir Shpilka","author":"Michael","year":"2013","unstructured":"Michael A. Forbes and Amir Shpilka. 2013. Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing. Springer Berlin Heidelberg, In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. isbn:978-3-642-40328-6 527-542."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","unstructured":"Francesco Galuppi and Mima Stanojkovski. 2021. Toric varieties from cyclic matrix semigroups. EUT Edizioni Universit\u00e0 di Trieste. doi:10.13137\/2464-8728\/33099 10.13137\/2464-8728\/33099","DOI":"10.13137\/2464-8728\/33099"},{"key":"e_1_2_1_20_1","unstructured":"Daniel R. Grayson and Michael E. Stillman. Macaulay2 a software system for research in algebraic geometry. Available at."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2024.41"},{"key":"e_1_2_1_22_1","volume-title":"Johnson","author":"Horn Roger A.","year":"2012","unstructured":"Roger A. Horn and Charles R. Johnson. 2012. Matrix Analysis. Cambridge University Press."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3614319"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209142"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3527458"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-63461-2_24"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9443-3"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6496"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","unstructured":"Lukas Katth\u00e4n Mateusz Micha\u0142ek and Ezra Miller. 2017. When is a Polynomial Ideal Binomial After an Ambient Automorphism? Foundations of Computational Mathematics 19 doi:10.1007\/s10208-018-9405-0 10.1007\/s10208-018-9405-0","DOI":"10.1007\/s10208-018-9405-0"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597066.3597109"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158142"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Serge Lang. 2002. Algebra. Springer New York. isbn:9781461300410 doi:10.1007\/978-1-4613-0041-0 http:\/\/dx.doi.org\/10.1007\/978-1-4613-0041-0 10.1007\/978-1-4613-0041-0","DOI":"10.1007\/978-1-4613-0041-0"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.IPL.2004.05.004"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Morris Newman. 1967. Two classical theorems on commuting matrices. 69. https:\/\/api.semanticscholar.org\/CorpusID:123327400","DOI":"10.6028\/jres.071B.013"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation. 129-138","author":"Nosan K.","unstructured":"K. Nosan, A. Pouly, S. Schmitz, M. Shirmohammadi, and J. Worrell. 2022. On the Computation of the Zariski Closure of Finitely Generated Groups of Matrices. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation. 129-138."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3286487"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/964001.964028"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.62"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3776698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T19:01:13Z","timestamp":1767898873000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3776698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":38,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2026,1,8]]}},"alternative-id":["10.1145\/3776698"],"URL":"https:\/\/doi.org\/10.1145\/3776698","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-07-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}