Computing automatic coset systems and subgroup presentations (Q1284217)

The authors give an algorithm to compute cosets of a group \(G\) with respect to a subgroup \(H\) and presentations of this subgroup. For this purpose, they define what is an automatic coset system which is the strict analogue of an automatic group, but the difference is that one gives each criterion in terms of a coset. So, if \(H=1\), one finds back the definition of an automatic group. The construction gives first a criterion when a group is shortlex coset automatic with respect to a given subgroup in terms of a word difference automaton. Then, a criterion is given with rather technical hypotheses when the automaton has indeed produced a coset system. The authors prove that the automaton produces a presentation of \(H\) if a presentation of \(G\) is given. The algorithm is implemented in the KBMAG package. In the thesis of I. D. Redfern such an algorithm is described, however no formal proof could be given there that the algorithm produces actually the correct result. The algorithm proposed in the paper under review shows to be faster and it is proven that the result it provides is correct. But, the hypotheses are more restrictive. Nevertheless, the authors could not find an example where their algorithm does not work, but Redfern's does.