On the Complexity of Properties of Transformation Semigroups

Trevor Jack

Published 2018-10-31Version 1

We investigate the computational complexity for determining various properties of a finite transformation semigroup $S$ given by generators. In particular, we show that checking whether an element of $S$ is regular is PSPACE-complete. We give polynomial time algorithms for enumerating left/right identities, finding a left/right zero, checking nilpotence, and checking if a semigroup satisfies a fixed equation.