The uniform word problem for groups and finite Rees quotients of \(E\)-unitary inverse semigroups (Q1403857)

Let \(\mathcal C\) be a pseudovariety of finite groups; the following two algorithmic problems are shown to be equivalent: (i) the decidability of the uniform word problem for \(\mathcal C\), and (ii) the decidability of whether a finite, directed, labelled graph can be embedded into the Cayley graph of a group in \(\mathcal C\). These problems are furthermore equivalent to various other problems of this sort, e.g. (iii) the decidability of whether a finite inverse semigroup with \(0\) is a Rees quotient of an \(E\)-unitary inverse semigroup with maximal group homomorphic image in \(\mathcal C\). Various ramifications are also pointed out, for example, if \(\mathcal C\) is a class closed under taking subgroups then the decidability of (iii) implies the decidability of (ii) implies the decidability of (i). In particular, all these problems are undecidable for the classes of all finite groups and of all finite nilpotent groups. Applications to categories are also given: it is undecidable whether a finite cancellative category embeds into a groupoid or into a finite groupoid. In particular, there is a finite cancellative category that embeds into a groupoid, but not into a finite groupoid.