I must know how and when it began. I can't seem to find anything historical on this. All I know up to this point is that Todd-Coxeter method was created in 1936. And, "words"? How did they even arise in double coset enumeration? I need more. :)
You mention double coset enumeration. There is some historical comment in the paper
R. Brown, N. Ghani, A.Heyworth, C.D.Wensley), `String-rewriting systems for double coset systems', J. Symb. Comp. 41 (2006) 573-590.
also available from the arXiv . arXiv:math/0508391 .
The following comes from the Introduction:
"The primary alternative to Todd-Coxeter procedures for ordinary coset enumeration and computation of groups given by presentations is string rewriting. In finite settings the two approaches are comparable: certain problems being more effectively addressed by the enumerative method and others benefitting more from a rewriting approach. However, for cases involving infinitely many elements, rewriting rather than enumeration is the natural choice.
This paper demostrates how string rewriting can be applied to the problems of computing double cosets, giving a new alternative to the Todd-Coxeter methods which can further be applied to infinite groups."