License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.115
URN: urn:nbn:de:0030-drops-125226
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12522/
Go to the corresponding LIPIcs Volume Portal

Bumpus, Georgina ; Haase, Christoph ; Kiefer, Stefan ; Stoienescu, Paul-Ioan ; Tanner, Jonathan

On the Size of Finite Rational Matrix Semigroups

pdf-format:
LIPIcs-ICALP-2020-115.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{bumpus_et_al:LIPIcs:2020:12522,
  author =	{Georgina Bumpus and Christoph Haase and Stefan Kiefer and Paul-Ioan Stoienescu and Jonathan Tanner},
  title =	{{On the Size of Finite Rational Matrix Semigroups}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{115:1--115:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12522},
  URN =		{urn:nbn:de:0030-drops-125226},
  doi =		{10.4230/LIPIcs.ICALP.2020.115},
  annote =	{Keywords: Matrix semigroups, Burnside problem, weighted automata, vector addition systems}
}

Keywords: Matrix semigroups, Burnside problem, weighted automata, vector addition systems
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI