Parallel algorithms for solvable permutation groups (Q1111023): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:15, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parallel algorithms for solvable permutation groups |
scientific article |
Statements
Parallel algorithms for solvable permutation groups (English)
0 references
1988
0 references
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.
0 references
solvable permutation groups
0 references
parallel complexity
0 references
automorphism of graphs
0 references
parallel algorithms
0 references
nilpotent groups
0 references
power commutator basis
0 references