文章基本信息

标题：On the Size of Finite Rational Matrix Semigroups
本地全文：下载
作者：Georgina Bumpus ; Christoph Haase ; Stefan Kiefer 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：115:1-115:13
DOI：10.4230/LIPIcs.ICALP.2020.115
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Matrix semigroups; Burnside problem; weighted automata; vector addition systems