We will consider the computational complexity of decision problems in which we are given a set of $n$-by-$n$ matrices over a finite field and asked to verify properties of the semigroup they generate. We give polynomial time algorithms for checking each of the following problems: (1) checking if the semigroup is a group, (2) enumerating left and right identities, and (3) checking if the semigroup is nilpotent.
Online Zoom meeting
(Univ. NOVA of Lisbon / CMA)
Semigroups, Automata and Languages