The class of strongly $0$-$E$-Unitary inverse semigroups is not recursive

Benjamin Steinberg

The class of strongly $0$-$E$-Unitary inverse semigroups was independently introduced by Bulman-Flemming, Fountain and Gould and by Lawson. They are inverse semigroups $S$ with $0$ with an idempotent pure partial homomorphism $f:S\setminus0\longrightarrow G$ where $G$ is a group. We show that the class of finite strongly $0$-$E$-Unitary inverse semigroups is not recursive.

More generally we prove the following theorem:

Theorem.The following are equivalent for a pseudovariety of (perhaps infinite) groups ${\bf V}$.

1. The Uniform Word Problem for ${\bf V}$ is decidable;
2. It is decidable if an inverse automaton embeds in the Cayley graph of some group from $\bf V$;
3. It is decidable if a finite inverse semigroup with zero removed has an idempotent pure partial homomorphism to a group in $\bf V$.