Permutation Group Algorithms

The algorithmic approach to permutation groups is one of the major areas of computational group theory, and it is also among its best developed parts. The book provides a rigorous exposition of the theory covering the present state of art. The main purpose is to describe the development of the past decade characterized by a significant convergence between theory concentrated on asymptotic analysis, and practical approach concerned with implementation. The convergence is represented by nearly linear-time complexity problems, which are the major theme of the book. The reader will find several dozen algorithms given mostly in narrative. The goal is to present the mathematics behind algorithms, and implementation details are omitted with some well motivated exceptions. Most of the algorithms are freely available in the well known GAP system. The ten sections include an introduction, a complexity overview, and a chapter dedicated to algorithms for black-box groups. The remaining seven sections discuss different problems for groups given by a generating set of permutations. From the theoretical point of view a significant part of the book is devoted to variants of Sim’s method relying on notions of base and strong generating set. The volume is an authoritative treatment of the subject and will be of lasting value to anybody interested in computational group theory.

Book details




User login