1 Search Results for "Stoienescu, Paul-Ioan"


Document
Track B: Automata, Logic, Semantics, and Theory of Programming
On the Size of Finite Rational Matrix Semigroups

Authors: Georgina Bumpus, Christoph Haase, Stefan Kiefer, Paul-Ioan Stoienescu, and Jonathan Tanner

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)


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.

Cite as

Georgina Bumpus, Christoph Haase, Stefan Kiefer, Paul-Ioan Stoienescu, and Jonathan Tanner. On the Size of Finite Rational Matrix Semigroups. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 115:1-115:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bumpus_et_al:LIPIcs.ICALP.2020.115,
  author =	{Bumpus, Georgina and Haase, Christoph and Kiefer, Stefan and Stoienescu, Paul-Ioan and Tanner, Jonathan},
  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 =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.115},
  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}
}
  • Refine by Author
  • 1 Bumpus, Georgina
  • 1 Haase, Christoph
  • 1 Kiefer, Stefan
  • 1 Stoienescu, Paul-Ioan
  • 1 Tanner, Jonathan

  • Refine by Classification
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Algebraic language theory
  • 1 Theory of computation → Quantitative automata

  • Refine by Keyword
  • 1 Burnside problem
  • 1 Matrix semigroups
  • 1 vector addition systems
  • 1 weighted automata

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail