{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:25:02Z","timestamp":1792070702296,"version":"4.4.0"},"reference-count":76,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We consider membership problems for rational subsets of the semigroup of [Formula: see text] matrices over [Formula: see text]. For a semigroup [Formula: see text], the rational subsets [Formula: see text] are defined as the sets accepted by nondeterministic finite automatons whose transitions are labeled by elements of [Formula: see text]. In general, it is undecidable on inputs [Formula: see text] and [Formula: see text] whether [Formula: see text] belongs to [Formula: see text]. Therefore, we restrict our attention to the family [Formula: see text] of flat rational subsets of [Formula: see text] over [Formula: see text], where [Formula: see text] is a subsemigroup of [Formula: see text]. It consists of finite unions of the form [Formula: see text], where [Formula: see text] and [Formula: see text]. Assuming that the membership for [Formula: see text] is decidable, we prove various results when the membership for [Formula: see text] is decidable. If [Formula: see text] is a subgroup of a group [Formula: see text], then we provide a rather general condition when [Formula: see text] is an (effective) relative Boolean algebra. This leads to one of our main results that the emptiness problem for Boolean combinations of sets in [Formula: see text] is decidable. It is possible that such a strong decidability result cannot be pushed any further for groups sitting between [Formula: see text] and [Formula: see text]. To support this possibility, we prove the following dichotomy: If [Formula: see text] is a finitely generated group such that [Formula: see text], then either [Formula: see text] or [Formula: see text] contains an extension of the Baumslag\u2013Solitar group [Formula: see text] of infinite index. It is open whether the membership for rational subsets is decidable in the latter case. For singular matrices, we will show that the membership problem for [Formula: see text] is decidable in doubly exponential time, where [Formula: see text] is the monoid generated by [Formula: see text].<\/jats:p>","DOI":"10.1137\/22m1512612","type":"journal-article","created":{"date-parts":[[2024,12,5]],"date-time":"2024-12-05T15:15:16Z","timestamp":1733411716000},"page":"1663-1708","source":"Crossref","is-referenced-by-count":1,"title":["Decidability of Membership Problems for Flat Rational Subsets of \\(\\boldsymbol{{\\textrm{GL}}(2,\\boldsymbol{{\\mathbb{Q}}})}\\) and Singular Matrices"],"prefix":"10.1137","volume":"53","author":[{"given":"Volker","family":"Diekert","sequence":"first","affiliation":[{"name":"Formale Methoden der Informatik, Universit\u00e4t Stuttgart, 70569 Stuttgart, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Igor","family":"Potapov","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Liverpool L69 3GJ, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7547-6391","authenticated-orcid":true,"given":"Pavel","family":"Semukhin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Liverpool John Moores University, Liverpool L3 3AF, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,12,3]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02088289"},{"key":"ref2","first-page":"695","volume":"11","author":"Anisimow A. V.","year":"1975","journal-title":"Elektron. Informationsv. Kybernetik"},{"key":"ref3","volume-title":"On Product and Sum Decompositions of Sets: The Factorization Theory of Power Monoids","author":"Antoniou A. A.","year":"2019"},{"key":"ref4","first-page":"498","author":"Babai L.","year":"1996","journal-title":"Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1962-10745-9"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1968-144-7"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196708004925"},{"key":"ref8","unstructured":"P. Bell, I. Potapov, and P. Semukhin, On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond, in 44th International Symposium on Mathematical Foundations of Computer Science, LIPIcs, Vol. 138, P. Rossmanith, P. Heggernes, and J.P. Katoen, eds. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2019, pp. 83:1\u201383:15."},{"key":"ref9","first-page":"105","author":"Bell P. C.","year":"2023","journal-title":"Inform. Comput."},{"key":"ref10","unstructured":"M. Benois, Parties rationelles du groupe libre, C. R. Acad. Sci. Paris S\u00e9r. A, 269 (1969), pp. 1188\u20131190."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0016231"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9771-7"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.2307\/1970103"},{"key":"ref14","first-page":"116:1","volume-title":"47th International Colloquium on Automata, Languages, and Programming, LIPIcs, Vol. 168","author":"Cadilhac M.","year":"2020"},{"key":"ref15","unstructured":"J. Cassaigne, V. Halava, T. Harju, and F. Nicolas, Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More, preprint, arXiv:1404.0644, 2014."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.03.001"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, Vols. 1, 2, American Mathematical Society, Providence, RI, 1961, 1967.","DOI":"10.1090\/surv\/007.1\/01"},{"key":"ref18","first-page":"44:1","volume-title":"46th International Colloquium on Automata, Languages, and Programming,LIPIcs","volume":"132","author":"Colcombet T.","year":"2019"},{"key":"ref19","series-title":"Graduate Texts in Mathematics 228","volume-title":"A First Course in Modular Forms","author":"Diamond F.","year":"2005"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196720500198"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1515\/9783110413335"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/3373207.3404038"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1142\/2563"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1142\/S021819671750028X"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/063"},{"key":"ref26","volume-title":"Automata, Languages, and Machines","author":"Eilenberg S.","year":"1974"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(69)90070-2"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1081\/AGB-120022785"},{"key":"ref29","first-page":"12:1","volume-title":"Proceedings 30th International Conference on Concurrency Theory, LIPIcs, Vol. 140","author":"Finkel A.","year":"2019"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721212.026"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-58.1.74"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9730-4_9"},{"key":"ref33","unstructured":"Z. Grunschlag, Algorithms in Geometric Group Theory, Ph.D. thesis, University of California, 1999, https:\/\/www.proquest.com\/dissertations-theses\/algorithms-geometric-group-theory\/docview\/304523226\/se-2?accountid=12118."},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1137\/050643295"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780199219858.001.0001"},{"key":"ref36","doi-asserted-by":"crossref","unstructured":"T. Harju, Post correspondence problem and small dimensional matrices, in Proceedings of the 13th International Conference on Developments in Language Theory, Lecture Notes in Computer Science 5583, V. Diekert and D. Nowotka, eds. Springer-Verlag, Berlin, 2009, pp. 39\u201346.","DOI":"10.1007\/978-3-642-02737-6_3"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1991250302551"},{"key":"ref38","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-29.4.428"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1137\/0208040"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882618-002"},{"key":"ref42","series-title":"LIPIcs, Vol. 107","first-page":"132:1","volume-title":"45th International Colloquium on Automata, Languages, and Programming","author":"Ko S.","year":"2018"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/677\/13625"},{"key":"ref44","series-title":"Memoirs of the American Mathematical Society 87","volume-title":"Hecke Algebras","author":"Krieg A.","year":"1990"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-023-10122-2"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_43"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2007.08.025"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2011.565258"},{"key":"ref49","series-title":"Classics in Mathematics","volume-title":"Combinatorial Group Theory","author":"Lyndon R.","year":"1977"},{"key":"ref50","first-page":"539","volume":"57","author":"Markov A. A.","year":"1947","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"ref51","first-page":"587","volume":"55","author":"Markov A. A.","year":"1947","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1964.14.1343"},{"key":"ref53","first-page":"1103","volume":"119","author":"Mihailova K. A.","year":"1958","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-07-02017-0"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1255632506"},{"key":"ref56","first-page":"1","volume":"44","author":"Novikov P. S.","year":"1955","journal-title":"Trudy Mat. Inst. Steklov."},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2022.10.023"},{"key":"ref58","volume-title":"Computational Complexity","author":"Papadimitriou Ch H.","year":"1994"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1970491105"},{"key":"ref60","first-page":"95","volume":"9","author":"Potapov I.","year":"2019","journal-title":"Dagstuhl Rep."},{"key":"ref61","doi-asserted-by":"crossref","unstructured":"I. Potapov and P. Semukhin, Decidability of the membership problem for \\(2\\times 2\\) integer matrices, in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, 2017, pp. 170\u2013186.","DOI":"10.1137\/1.9781611974782.12"},{"key":"ref62","unstructured":"I. Potapov and P. Semukhin, Membership problem in GL(2, \\(\\mathbb{Z}\\)) extended by singular matrices, in 42nd International Symposium on Mathematical Foundations of Computer Science, LIPIcs, Vol. 83, K. G. Larsen, H. L. Bodlaender, and J.F. Raskin, eds. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2017, pp. 44:1\u201344:13."},{"key":"ref63","first-page":"92","volume-title":"Comptes-rendus du premier congr\u00e8s des mathematiciens des pays slaves, Warszawa 1929","author":"Presburger M.","year":"1930"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1007\/b104443"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1007\/BF01462922"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023848"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289520"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242355"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1007\/BF02952517"},{"key":"ref70","first-page":"55","volume":"8","author":"Sch\u00fctzenberger M.-P.","year":"1974","journal-title":"Rev. Fran\u00e7aise Autom. Inform. Rech. Op\u00e9r. S\u00e9r. Rouge"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1007\/BF02194921"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050045"},{"key":"ref73","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61856-7"},{"key":"ref74","first-page":"195","volume":"77","author":"Silva P. V.","year":"2002","journal-title":"Bull. EATCS"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1017\/S0013091500008221"},{"key":"ref76","unstructured":"Y.Y. Tran, Computably Enumerable Boolean Algebras, Ph.D. thesis, Cornell University, 2018, https:\/\/doi.org\/10.7298\/X4Z60M82, https:\/\/ecommons.cornell.edu\/items\/825e1b2b-4f48-4df7-8cfa-b6716ea96459."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1512612","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:16:19Z","timestamp":1787339779000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1512612"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,3]]},"references-count":76,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1137\/22M1512612"],"URL":"https:\/\/doi.org\/10.1137\/22m1512612","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,3]]}}}