< ^ From:

< ^ Subject:

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

> < [top]