On the computational complexity of the Abelian permutation group structure, membership and intersection problems
type: Item
instance of: scholarly article
title: On the computational complexity of the Abelian permutation group structure, membership and intersection problems
zbMATH Open document ID: 0652.20001
DOI: 10.1016/0304-3975(88)90078-3
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: 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''.
reviewed by: K. G. Brokate
Mathematics Subject Classification ID: 20-04
Mathematics Subject Classification ID: 20K01
Mathematics Subject Classification ID: 20B35
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4063339
zbMATH Keywords: product of cycles
zbMATH Keywords: cyclic subgroups
zbMATH Keywords: base element
zbMATH Keywords: orbits
zbMATH Keywords: membership- relation
zbMATH Keywords: intersection of permutation groups
zbMATH Keywords: algorithms
author: Costas S. Iliopoulos
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90078-3
OpenAlex ID: W1978556944
cites work: Q4091421
cites work: Fast parallel matrix and GCD computations
cites work: Q5534298
cites work: Group-theoretic algorithms and graph isomorphism
cites work: Q5595961
cites work: Q3197327
cites work: Analysis of algorithms on problems in general abelian groups
cites work: Monte Carlo circuits for the abelian permutation group intersection problem
cites work: Q3705594
cites work: Q5585021
cites work: Q5512231
description: scientific article; zbMATH DE number 4063339