2026-09-08T01:21:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26574 2026-09-05T19:47:14Z ddc:004 open_access

Revisiting Finiteness of Matrix Monoids Ait El Manssour, Rida Guttenberg, Roland Lhote, Nathan Shirmohammadi, Mahsa Worrell, James Ben Matrix Semigroups Finiteness Integrality Bitsize Bound This paper concerns decision problems related to finite monoids of rational matrices. We show that determining finiteness of a given finitely presented monoid is in PSpace, improving the known coNExp^NP bound. We also show that the membership problem for finite matrix monoids is PSpace-complete, improving the known NExp-upper bound. Our two complexity results are corollaries of a new polynomial bit-size bound on matrix entries in finite monoids. This is obtained by reduction to the case of matrix groups, using the structure theory of noncommutative algebras and of matrix monoids. Our techniques also give us a polynomial-time algorithm for deciding whether a monoid of rational matrices is conjugate to a monoid of integer matrices. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rida Ait El Manssour and Roland Guttenberg and Nathan Lhote and Mahsa Shirmohammadi and James Ben Worrell 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.158 urn:nbn:de:0030-drops-265745 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.158 eng https://creativecommons.org/licenses/by/4.0/legalcode