eprintid: 10096879
rev_number: 24
eprint_status: archive
userid: 608
dir: disk0/10/09/68/79
datestamp: 2020-05-07 13:45:50
lastmod: 2020-10-22 08:23:52
status_changed: 2020-10-22 08:23:52
type: proceedings_section
metadata_visibility: show
creators_name: Bumpus, G
creators_name: Haase, C
creators_name: Kiefer, S
creators_name: Stoienescu, P-I
creators_name: Tanner, J
title: On the Size of Finite Rational Matrix Semigroups
ispublished: pub
divisions: UCL
divisions: A01
divisions: B04
divisions: C05
divisions: F48
note: 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.
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.
date: 2020-06-29
date_type: published
publisher: Schloss Dagstuhl--Leibniz-Zentrum
official_url: https://doi.org/10.4230/LIPIcs.ICALP.2020.115
oa_status: green
full_text_type: pub
language: eng
primo: open
primo_central: open_green
verified: verified_manual
elements_id: 1780281
doi: 10.4230/LIPIcs.ICALP.2020.115
lyricists_name: Haase, Christoph
lyricists_id: CHAAS66
actors_name: Haase, Christoph
actors_id: CHAAS66
actors_role: owner
full_text_status: public
series: Leibniz International Proceedings in Informatics (LIPIcs)
place_of_pub: Dagstuhl, Germany
pagerange: 115
event_title: 47th International Colloquium on Automata, Languages and Programming (ICALP 2020)
institution: 47th International Colloquium on Automata, Languages and Programming (ICALP 2020)
issn: 978-3-95977-138-2
book_title: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
citation:        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   
 
document_url: https://discovery-pp.ucl.ac.uk/id/eprint/10096879/1/Haase_LIPIcs-ICALP-2020-115.pdf