Dear gap forum:
As there has been discussion about the AbStab.g package, I need to respond.

I would like to describe some algorithms used in my package, AbStab.g, to
express an element of permutation group as a word in the generators.
We start by constructing a stabilizer chain in a manner similar to
MakeStabilizerChain. For each subgroup in the stabilizer chain, the generators
are stored both as permutations and as abstract words, derived from the
generators of the next larger stabilizer subgroup.
Let H represent a subgroup in the stabilizer chain, and K the next subgroup
in the chain. (K is the stabilizer in H of some point p.) Let the generators
of H be {g1, ..., gk}. The generators of K are found by first taking a left
Schreier transversal for the cosets of H in K with respect to these generators.
For each x in H, let \overbar{x} be the element of the Schreier transversal
which represents the same coset stabilizer. Then H may be generated by the
elements { u^-1 * gi * \overbar{u^-1 * gi} }, where u ranges over the elements
of the Schreier transversal, and gi ranges over the generators of H. (As p is
the point stabilized, u^-1 * gi * \overbar{u^-1 * gi} :p -> k -> q -> p, when
following the action of each element of the multiplication, i.e. p^u = k...)
(see D.L. Johnson, Presentations of groups (1990) )
This set of elements is often much larger than needed. We sort them
according to length. The function MinGenSet then adjoins these generators
one by one, in order of length, starting with the shortest. If the next
generator actually increases the size of the subgroup generated, it is retained,
otherwise it is discarded. We finish with a small list of short generators for
the stabilizer K. This is repeated to stabilize the next point, until the
trivial subgroup is obtained.

Once the abstract stabilizer chain has been found, it is fairly trivial to
take an element x of the group and find an expression for it as a word in the
generators of the group. Assume that G is a permutation group on { 1..n }.
For each point p let Gp represent the stabilizer of [1..p-1] in G. Let x_p
denote an element of Gp obtained inductively with p, starting with x_1=x. We
let x_{p+1} := x_p * s, where s is the element of the Schreier transversal of
the form (p^x_p, p, ....). Then x_{p+1} will fix the point p. This causes
x_n = (). (If x_n <> (), then x was not in the group to begin with.) This
results in an expression for x.

The function Shrink attempts to find a shorter representation for an
element of G. Let x be in G, and g*w represent x as a product of generators,
g a generator, and w a word. Then look for the shortest word in the following
lists: {w}, {FactorPermGroupElement(h*x) | h or h^-1 in G.generators},
{FactorPermGroupElement(x*h) | h or h^-1 in G.generators}.
Then replace g*w by g'*w' or w'*g', where w' is this shortest word, and
g' =g or h, as above. The is repeated with w', until w' is of length 1.

I now give an example of AbStab.g. Note the method used for choosing the
names of the abstract generators.

...
gap> gen:=Set([f1,f2,f3,f4,r1,r2,r3,r4]);
[ (25,26,27,28,29,30,31,32), (17,18,19,20,21,22,23,24),
  ( 9,10,11,12,13,14,15,16), ( 4,31)( 5,30)( 6,29)( 7,28)(12,23)(13,22)(14,21)
    (15,20), ( 3,30)( 4,29)( 5,28)( 6,27)(11,22)(12,21)(13,20)(14,19),
  ( 2,29)( 3,28)( 4,27)( 5,26)(10,21)(11,22)(12,23)(13,24), (1,2,3,4,5,6,7,8),
  ( 1,28)( 2,27)( 3,26)( 4,25)( 9,20)(10,19)(11,18)(12,17) ]
gap> G := Group(gen,());;
gap> G.abstractGenerators := Union(AbstractGenerators("f",4),
>                               AbstractGenerators("r",4) );
[ f1, f2, f3, f4, r1, r2, r3, r4 ]
gap> 2_cycle:=(1,2);
(1,2)
gap> cycle2a:=FactorPermGroupElement(G,2_cycle);
f1^2*r1*r3* ... *r3^-1*r1^-1*f1^-2
<< a word of length 409 >>
gap> cycle2b:=Shrink(G,cycle2a);
f1^-2*r1^-1*f1* ... *r1^-1*r3^-1*r1^-1
<< a word of length 107 >>
gap> cycle2d := Shrink(G,(1,2));;
gap> cycle2d = cycle2c;
true
gap> map( G, cycle2a );
( 1, 2)
gap> map( G, cycle2b );
( 1, 2)
gap>

By no means does this package claim to give the shortest solution. It may
be observed that asking the points to be stabilized in a different order may
make a significant difference on the length of a solution given (both in length
of word and time.)
Finally I should note that there are a number of aspects of these routines
which ideally should be reworked to make them more efficient and robust.

There is a small change that should be made to one of the functions, due
to a change of the implementation of the function List. This suggestion was
made by Heiko Theissen:

--- AbStab.g.orig   Fri Oct 28 21:34:03 1994 # GAP V3R4P2 (or earlier)
+++ AbStab.g    Wed Jan 31 10:41:19 1996     # GAP V3R4P3
@@ -210,8 +210,10 @@
     lt:=LeftSchreier(arg);
     alt:= lt.ASchreier;
     lt := lt.Schreier;
-    rt:=List(lt,x->x^-1);
-    art:=List(alt,x->x^-1);
+    # rt:=List(lt,x->x^-1);
+    # art:=List(alt,x->x^-1);
+    rt:=[]; for x in lt do Add( rt, x^-1 ); od;
+    art:=[]; for x in alt do Add( art, x^-1 ); od;
     for g in G.generators do
        i:=Position(G.generators, g);
        ag := G.abstractGenerators[i];

This should fix any problems, as all other calls to the function "List" do
not implement a list with gaps in it.

Philip Osterlund
February 9, 1996
University of Minnesota
osterlu@math.umn.edu