Polytime Decision Problems Involving Finite Matrix Semigroups

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

Area

Semigroups, Automata and Languages

Financiamento