Finding when a relator can be removed from group presentation

Question

There are 4 Tietze transformations and one of them is removal of superfluous relator. Is there a mechanical approach/algorithm for deciding which relators can be removed and which cannot?

Answer 1

A relator $R_n$ can be removed if it can be derived from the other ones $R_1...R_{n-1}$. In order to check if such derivation is possible you need to check if $R_n=e$ in group $\langle A| R_1...R_{n-1} \rangle$. This is called word problem and is undecidable (so there is no algorithm).

However, you can do something else. If the group is finite, you can use perform enumeration of cosets. This way you can find Cayley graph, Schreier transversal, permutation representation and most importantly a definition table with all relations necessary for the group. While this does not tell you which of the original relations were superfluous, you may use the "definition" column in monitor table to produce a new set of relators.

It is also worth mentioning the Knuth-Benedix algorithm for solving the word problem. You may use it to semi-decide whether a relator is not superfluous, but Knuth-Benedix may fail if the relator is superfluous.