UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

On the Size of Finite Rational Matrix Semigroups

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. Green open access

[thumbnail of Haase_LIPIcs-ICALP-2020-115.pdf]
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.

Type: Proceedings paper
Title: On the Size of Finite Rational Matrix Semigroups
Event: 47th International Colloquium on Automata, Languages and Programming (ICALP 2020)
Open access status: An open access version is available from UCL Discovery
DOI: 10.4230/LIPIcs.ICALP.2020.115
Publisher version: https://doi.org/10.4230/LIPIcs.ICALP.2020.115
Language: English
Additional information: This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/3.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10096879
Downloads since deposit
14Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item