On the size of finite rational matrix semigroups

Conference item

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.

Authors: Bumpus, G; Haase, C; Kiefer, S; Stoienescu, P-I; Tanner, J

• Alternative title: Conference paper
• Publication status: Published
• Peer review status: Reviewed (other)
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
• Journal: Leibniz International Proceedings in Informatics
• Volume: 168
• Article number: 115
• Publication date: 2020-06-29
• Acceptance date: 2020-04-15
• Event title: 47th International Colloquium on Automata, Languages and Programming (ICALP 2020)
• Event location: Saarbrücken, Germany
• Event website: https://icalp2020.saarland-informatics-campus.de/
• Event start date: 2020-07-08
• Event end date: 2020-07-11
• DOI: 10.4230/LIPIcs.ICALP.2020.115
• ISSN: 1868-8969
• ISBN: 9783959771382
• Language: English
• Keywords: FFR; Burnside problem; weighted automata; matrix semigroups; vector addition systems