On the computational complexity of the Abelian permutation group structure, membership and intersection problems (Q1106934): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Costas S. Iliopoulos / rank | |||
Property / author | |||
Property / author: Costas S. Iliopoulos / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(88)90078-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1978556944 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4091421 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast parallel matrix and GCD computations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5534298 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Group-theoretic algorithms and graph isomorphism / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5595961 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3197327 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Analysis of algorithms on problems in general abelian groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Monte Carlo circuits for the abelian permutation group intersection problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3705594 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5585021 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5512231 / rank | |||
Normal rank |
Latest revision as of 18:27, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the computational complexity of the Abelian permutation group structure, membership and intersection problems |
scientific article |
Statements
On the computational complexity of the Abelian permutation group structure, membership and intersection problems (English)
0 references
1988
0 references
Considered are groups defined by a set of permutations of a carrier each given as a product of cycles, disjoint within that product. In addition the groups are assumed Abelian (and finite) - which imposes a severe restriction on the cycles, when overlapping. - Deriving the complete structure of a group defined in such a manner is a complex task. The proposed algorithm - used in a proof for obtaining a limit for the complexity, and being the main essence of the reviewed paper - tries to exploit the idea to derive a base (with its exponents) by splitting the group into a Cartesian product of disjoint factors, or at least more generally by finding a supergroup with such a splitting. Hopefully these factors are cyclic - or at least decomposable into a product of disjoint cyclic subgroups each with an easily derivable base element: The complexity then is the ``sum'' of the complexities for the factors and no longer of about the order of their product. The presented derivation relies heavily on earlier publications of the author. Its goal is: partitions of the carrier into orbits as much disjoint as possible, each one covering overlapping cycles of the definition, so that each cycle is covered by some orbit. Besides the derivation also the computation of the membership-relation, and intersection of permutation groups is considered. The respective algorithms given are dependent on the afore mentioned procedure. For all computations limits or estimates of the required machine operations are given. - Author's correction: line 2, pg. 214 ``... for fixed j'' read ``... for fixed i''.
0 references
product of cycles
0 references
cyclic subgroups
0 references
base element
0 references
orbits
0 references
membership- relation
0 references
intersection of permutation groups
0 references
algorithms
0 references