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.

## Date and Venue

Start Date

Venue

Online Zoom meeting

End Date

## Speaker

Trevor Jack

## Speaker's Institution

(Univ. NOVA of Lisbon / CMA)

## Files

Trevor Jack-30Apr2021.pdf409.21 KB

## Area

Semigroups, Automata and Languages