2026-07-22T10:24:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12522 2024-03-06T10:50:21Z ddc:004 open_access

On the Size of Finite Rational Matrix Semigroups Bumpus, Georgina Haase, Christoph Kiefer, Stefan Stoienescu, Paul-Ioan Tanner, Jonathan Matrix semigroups Burnside problem weighted automata vector addition systems Let n be a positive integer and M a set of rational n × n-matrices such that M generates a finite multiplicative semigroup. We show that any matrix in the semigroup is a product of matrices in M whose length is at most 2^{n (2 n + 3)} g(n)^{n+1} ∈ 2^{O(n² log n)}, where g(n) is the maximum order of finite groups over rational n × n-matrices. This result implies algorithms with an elementary running time for deciding finiteness of weighted automata over the rationals and for deciding reachability in affine integer vector addition systems with states with the finite monoid property. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Georgina Bumpus and Christoph Haase and Stefan Kiefer and Paul-Ioan Stoienescu and Jonathan Tanner 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.115 urn:nbn:de:0030-drops-125226 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.115 eng https://creativecommons.org/licenses/by/3.0/legalcode