Nie jesteś zalogowany |
Revisiting Finiteness of Matrix Monoids
- Prelegent(ci)
- Roland Guttenberg
- Afiliacja
- University of Warsaw
- Język referatu
- angielski
- Termin
- 18 lutego 2026 14:15
- Pokój
- p. 5440
- Tytuł w języku polskim
- Revisiting Finiteness of Matrix Monoids
- Seminarium
- Seminarium „Teoria automatów”
This paper concerns decision problems related to finite monoids of rational matrices.
We show that determining finiteness of a given finitely presented matrix monoid is in \pspace, improving the
known $\conexp^{\np}$ bound. We also show that the membership problem for finite matrix monoids is \pspace-complete, improving the known \nexp-upper bound.
Our two complexity
results are corollaries of a new polynomial bit-size bound on matrix entries in finite monoids.
This is obtained by reduction to the case of matrix groups, using the structure theory of noncommutative algebras
and of matrix monoids.
Our techniques also give us a polynomial-time algorithm for deciding whether a monoid of rational matrices is conjugate to a monoid of integer matrices.
