On the Size of Finite Rational Matrix Semigroups

DOI10.4230/LIPICS.ICALP.2020.115MaRDI QIDQ6325050zbMATH OpenFDO

Authors Georgina Bumpus, Christoph Haase, Stefan Kiefer, Paul-Ioan Stoienescu, Jonathan W. Tanner

Publication date 9 September 2019

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.115

Abstract: Let $n$ be a positive integer and $mathcalM$ a set of rational $nimesn$-matrices such that $mathcalM$ generates a finite multiplicative semigroup. We show that any matrix in the semigroup is a product of matrices in $mathcalM$ whose length is at most $2^{n(2n+3)}g(n{)}^{n+1}in{2}^{O(n^{2}logn)}$, where $g(n)$ is the maximum order of finite groups over rational $nimesn$-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.

This page was built for publication: On the Size of Finite Rational Matrix Semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325050)