On the computational complexity of the Abelian permutation group structure, membership and intersection problems (Q1106934)

From MaRDI portal
Revision as of 02:04, 31 January 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references