Dear Forum Members,
Christopher Jefferson asked about the complexity of stabilizer chain
computations in permutation groups. Given G=<S> \le S_n,
generators for the point stabilizers (called a strong generating set)
can indeed be computed in polynomial time in |S| and n. The first
algorithm was given in
C. Sims: Computation with permutation groups, Proc. Second Symp. on
Symbolic and Algebraic Manipulation, ACM Press, 1971, pp. 23--28.
The first analysis that a version of Sims's algorithm runs in polynomial
time appeared in
M. Furst, J. Hopcroft, E. Luks: Polynomial-time algorithms for
permutation groups, Proc. 21st IEEE Symp. on Foundations of Computer
Science, IEEE Press, 1980, pp. 36--41.
The current asymptotically fastest strong generating set construction
is in
L. Babai, E. Luks, \'A. Seress: Fast management of permutation groups I, SIAM J. Computing 26 (1997), 1310--1342.
As a blatant self-advertisement, I'd like to mention that various strong
generating set constructions, and many more permutation group algorithms,
are described in my forthcoming book
\'A. Seress: Permutation Group Algorithms, Cambridge Univ. Press, 2002.
Best regards,
Akos Seress