Collection from the left and other strategies (Q802744)

Any finite soluble group G has a presentation of the form \[ G=<g_ 1,...,g_ n| \quad g_ i^{p_ i}=w_{ii},\quad g_ jg_ i=g_ iw_{ij},\quad 1\leq i<j\leq n> \] where \(p_ i\in N\) and \(w_{ij}\) is a word in \(g_{i+1},...,g_ n\). With respect to such a generating set, each element of G can be represented by an ordered and normed word and multiplication of such words can be performed by a ``collection'' process. This idea and the term ``collection'' dates back at least to \textit{Ph. Hall}'s great paper ``A contribution to the theory of groups of prime power order'' [Proc. Lond. Math. Soc., II. Ser. 36, 29-95 (1933; Zbl 0007.29102)]; it has been used in computer-implementations since 1960 [the reviewer, Numer. Math. 3, 271-278 (1961; Zbl 0109.355)] and it has found its most important application with the successive calculation of the factors of the lower p-central series of a finitely presented group [\textit{I. D. Macdonald}, J. Aust. Math. Soc. 17, 102-112 (1974; Zbl 0277.20024) and \textit{M. F. Newman}, Symbolic and algebraic computation 2-8 (1976; Zbl 0455.20002)]. It can easily be seen that any given unordered word in the above generators can be transformed eventually into an ordered normed word, if one continues to replace any occurring subword which is equal to the left hand side of one of the relators by its right hand side. However, the efficiency of such procedure depends crucially on the strategy of choosing the next subword to be replaced. The authors give convincing experimental evidence, and some theoretical model in the case of p-groups, for their claim, that choosing each time the leftmost subword to which a relator of the second kind can be applied, is superior in most cases to a previously frequently used strategy by which the rightmost subword was replaced. The paper offers a well balanced discussion of careful experimentation, heuristic analysis and finally some proven facts; it provides a challenge to people interested in complexity analysis to further clarify the situation for finite soluble groups (and also for infinite polycyclic groups which are presently getting more and more algorithmic attention). However, when such complexity analysis is undertaken, it should be carried out with the same attention to practical application that is the special merit of the present paper.