Parallel algorithms for solvable permutation groups

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Software, source code, etc. for problems pertaining to group theory (20-04) General theory for finite permutation groups (20B05) Finite solvable groups, theory of formations, Schunck classes, Fitting classes, (pi)-length, ranks (20D10) Series and lattices of subgroups (20D30) Generators, relations, and presentations of groups (20F05) Analysis of algorithms and problem complexity (68Q25)

Review text

Here is an elaborated extension of a recently published work [the second author and \textit{St. A. Cook}, SIAM J. Comput. 16, 880-909 (1987; Zbl 0647.68045)] on the complexity of algorithms for decisions with permutation groups and for deriving of interesting subgroups thereof. Considered are (again) groups defined by a finite list of generating permutations on a carrier (set of points) of given finite degree n: For the class of soluble groups existence and outline of fast parallel algorithms are proved/presented which handle tests for solubility, and for membership, computation of order, centralizer, center, (derived) series of commutator subgroups, composition series, and some more for the subclass of nilpotent groups. An application to automorphism groups of a certain class of vertex- coloured graphs is shown as of the same fastness (i.e., belonging into the earlier defined class NC). The main tool is the power commutator basis (PCB) defined and existing exactly for soluble groups G: \(g\in G\) iff \(g=\prod b_ i^{\epsilon_ i}\) with \(1\leq i\leq m\), \(b_ i\in G\), \(0\leq \epsilon_ i<\rho_ i>1\), whereby the subgroups \(<b_ i,...,b_ m>\) constitute a subnormal series, and \(ord(G)=\prod \rho_ i.\) The basis for the derivations of the complexity for the proposed problems is a lemma on the complexity for the computation of a linear base of all the products of a fixed finite set of linear transformations (including identity) of the space \({\mathbb{Z}}_ p^{\times d}\) (with prime p) which is shown to belong to class NC by recourse to some mentioned earlier results concerning linear algebra.

Recommendations

Cites work

Cited in

(14)

Describes a project that uses

Uses Software

Cayley

This page was built for publication: Parallel algorithms for solvable permutation groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111023)