Coset Enumeration can be considered as a means of constructing a permutation representation of a finitely-presented group. Let G be such a group, and let Omega= H \ G be the set of right cosets of a subgroup H, on which G acts. Let K be a subgroup of G. The action of K will divide Omega into orbits corresponding to the double cosets H \ G/K. Now, suppose that x in G and let L = K cap K^{x^{-1}}. Let D in H \ G/K be a double coset and let d be a fixed single coset contained in it (so that D=dK). Let l in L. Then (dl)x = (dx)l^x in (dx)K so that the action of x on Omega can be computed from its action on a set of orbit representatives of L and its action on L, which takes place within K. If L is large this can provide a considerable saving of space. This space saving is the motivation for double coset enumeration. The group L is called the bf gain group of x, since the space saving is approximately a factor of |L|.
The input to the double coset enumeration algorithm includes a specification of a group K, and of a set of generators X. For each x in X, a pair of subgroups L_x, L^{(x)} le K is given, together with an isomorphism theta_x : L_x rightarrow L^{(x)}. This information defines a group F, obtained from the free product of K with the free group F_X by requiring that each x act by conjugation on L_x according to the map theta_x. Technically F is a multiple HNN-extension of K.
The final parts of the input (mathematically speaking, in practice additional input is used to guide the program towards efficiency) are a set of relators R and a set of subgroup generators W, consisting of elements of the free product of K and F_X, that is words composed of the letters x and elements of K.
The algorithm then constructs a compact representation of the action of a group G = F/N, where N = < R> ^F, on the set Omega of cosets of H = < W> N/N. This can also be viewed as a permutation action of F, with kernel N and point stabiliser < W> N. We take this view to avoid writing KN/N all the time.
This representation is organized in terms of the orbits (double cosets)
of K on Omega. For each orbit D, an arbitrary representative d in
D is chosen, and the group M_d = Stab_K(d) is recorded (as a subgroup
of K). For historical reasons this group is known as the ``muddle
group of the double coset. This allows us to refer to elements of
Omega by expressions of the form dk, with
d_1k_1 = d_2k_2 iff d_1 = d_2 mbox and k_1k_2^-1in M_d_1.
We call such an expression a bf name for the element of Omega.
In addition for each x in X, and for each orbit of L_x contained in D, with representative dk, a name for the point dkx is recorded. By the arguments of the initial paragraph, the action of x on any dk can then be computed, and the action of K is by right multiplication, so the full action of F (or equivalently G) is available.
GAP 3.4.4