Bumpus, G; Haase, C; Kiefer, S; Stoienescu, P-I; Tanner, J; (2020) On the Size of Finite Rational Matrix Semigroups. In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). (pp. p. 115). Schloss Dagstuhl--Leibniz-Zentrum: Dagstuhl, Germany.

Preview

Text Haase_LIPIcs-ICALP-2020-115.pdf - Published Version Download (688kB) | Preview

Abstract

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.

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as JSONCSVXML

Downloads by country - last 12 months

Export as XMLCSVJSON

Archive Staff Only

View Item