  We examine the computational complexity of problems in which we are given
generators for a partial bijection semigroup and asked to check properties of
the generated semigroup. We prove that the following problems are in AC$^0$:
(1) enumerating left and right identities and (2) checking if the semigroup is
completely regular. We prove that checking membership of a given idempotent is
a PSPACE-complete problem. We also describe a nondeterministic logspace
algorithm for checking if an inverse semigroup given by generators satisfies a
given semigroup identity that may involve a unary inverse operation.
