You are not logged in |
Revisiting Finiteness of Matrix Monoids
- Speaker(s)
- Roland Guttenberg
- Affiliation
- University of Warsaw
- Language of the talk
- English
- Date
- Feb. 18, 2026, 2:15 p.m.
- Room
- room 5440
- Title in Polish
- Revisiting Finiteness of Matrix Monoids
- Seminar
- Seminar Automata Theory
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.
