Permutation Group Algorithms.

By: Seress, ÁkosSeries: Cambridge Tracts in MathematicsPublisher: New York : Cambridge University Press, 2003Copyright date: ©2003Description: 1 online resource (274 pages)Content type: text Media type: computer Carrier type: online resourceISBN: 9781139146166Subject(s): Permutation groupsGenre/Form: Electronic books. Additional physical formats: Print version:: Permutation Group AlgorithmsDDC classification: 512.2 LOC classification: QA175 .S47 2003Online resources: Click to View
Contents:
Cover -- Half-title -- Title -- Copyright -- Contents -- 1 Introduction -- Acknowledgments -- 1.1. List of Algorithms -- 1.2. Notation and Terminology -- 1.2.1. Groups -- 1.2.2. Permutation Groups -- 1.2.3. Algorithmic Concepts -- 1.2.4. Graphs -- 1.3.Classification of Randomized Algorithms -- 2 Black-Box Groups -- 2.1. Closure Algorithms -- 2.1.1. Orbit Computations -- 2.1.2.Closure of Algebraic Structures -- The Closure Algorithm -- Algorithms Based on Normal Closure -- 2.2. Random Elements of Black-Box Groups -- The Product Replacement Algorithm -- 2.3. Random Subproducts -- 2.3.1. Definition and Basic Properties -- 2.3.2. Reducing the Number of Generators -- 2.3.3. Closure Algorithms without Membership Testing -- 2.3.4. Derived and Lower Central Series -- 2.4. Random Prefixes -- 2.4.1. Definition and Basic Properties -- 2.4.2. Applications -- Exercises -- 3 Permutation Groups A Complexity Overview -- 3.1. Polynomial-Time Algorithms -- 3.2. Nearly Linear-Time Algorithms -- 3.3. Non-Polynomial-Time Methods -- 4 Bases and Strong Generating Sets -- 4.1. Basic Definitions -- The Sifting Procedure -- 4.2. The Schreier-Sims Algorithm -- The Schreier-Sims Algorithm -- 4.3. The Power of Randomization -- The Random Schreier-Sims Algorithm -- 4.4. Shallow Schreier Trees -- 4.5. Strong Generators in Nearly Linear Time -- The SGS Construction -- The Algorithm Solving (4.6) -- 4.5.1. Implementation -- Exercises -- 5 Further Low-Level Algorithms -- 5.1. Consequences of the Schreier-Sims Method -- 5.1.1. Pointwise Stabilizers -- 5.1.2. Homomorphisms -- 5.1.3. Transitive Constituent and Block Homomorphisms -- The Block Homomorphism Algorithm -- 5.1.4. Closures and Normal Closures -- 5.2. Working with Base Images -- 5.3. Permutation Groups as Black-Box Groups -- Representation as a Black-Box Group -- 5.4. Base Change.
The Exchange of Two Base Points (Deterministic Version) -- The Exchange of Two Base Points (Las Vegas Version) -- Base Change by Conjugation -- 5.5. Blocks of Imprimitivity -- 5.5.1. Blocks in Nearly Linear Time -- 5.5.2. The Smallest Block Containing a Given Subset -- Computation of the Smallest Block Containing… -- 5.5.3. Structure Forests -- Exercises -- 6 A Library of Nearly Linear-Time Algorithms -- 6.1. Special Case of Group Intersection and pplications -- 6.1.1. Intersection with a Normal Closure -- 6.1.2. Centralizer in the Symmetric Group -- 6.1.3. The Center -- 6.1.4. Centralizer of a Normal Subgroup -- 6.1.5. Core of a Subnormal Subgroup -- 6.2. Composition Series -- 6.2.1. Reduction to the Primitive Case -- 6.2.2. The O'Nan-Scott Theorem -- 6.2.3. Normal Subgroups with Nontrivial Centralizer -- Computing the Socle of a Frobenius Group -- Luks's Algorithm -- Neumann's Algorithm (the EARNS Subroutine) -- 6.2.4. Groups with a Unique Nonabelian Minimal Normal Subgroup -- The Algorithm for Case B of Theorem 6.2.7 -- The Algorithm for Case C(i) -- The Algorithm for Case C(ii) -- The Algorithm for Case C(iii) -- 6.2.5. Implementation -- 6.2.6. An Elementary Version -- Beals's Algorithm for Groups with Regular Normal Subgroups -- Beals's Algorithm for Groups with No Regular Normal Subgroups -- 6.2.7. Chief Series -- 6.3. Quotients with Small Permutation Degree -- 6.3.1. Solvable Radical and p-Core -- The Algorithms -- Exercises -- 7 Solvable Permutation Groups -- 7.1. Strong Generators in Solvable Groups -- The Generalized Normal Closure Algorithm -- 7.2. Power-Conjugate Presentations -- Conversion to a pcp -- 7.3. Working with Elementary Abelian Layers -- 7.3.1. Sylow Subgroups -- 7.3.2. Conjugacy Classes in Solvable Groups -- Computation of the Class Representatives -- Computation of the Centralizers -- 7.4. Two Algorithms for Nilpotent Groups.
7.4.1. A Fast Nilpotency Test -- 7.4.2. The Upper Central Series in Nilpotent Groups -- Exercises -- 8 Strong Generating Tests -- 8.1. The Schreier-Todd-Coxeter-Sims Procedure -- 8.1.1. Coset Enumeration -- 8.1.2. Leon's Algorithm -- The STCS Algorithm -- 8.2. Sims's Verify Routine -- The Verify Routine -- 8.3. Toward Strong Generators by a Las Vegas Algorithm -- 8.4. Short Presentation -- 9 Backtrack Methods -- 9.1. Traditional Backtrack -- 9.1.1. Pruning the Search Tree: Problem-Independent Methods -- 9.1.2. Pruning the Search Tree: Problem-Dependent Methods -- 9.2. The Partition Method -- 9.3. Normalizers -- 9.4. Conjugacy Classes -- Class Representatives by Random Sampling -- Representatives in Centralizers of p-Elements -- Separation of the Solvable Radical -- Exercises -- 10 Large-Base Groups -- 10.1. Labeled Branchings -- 10.1.1. Construction -- 10.2. Alternating and Symmetric Groups -- 10.2.1. Number Theoretic and Probabilistic Estimates -- 10.2.2. Constructive Recognition: Finding the New Generators -- 10.2.3. Constructive Recognition: The Homomorphism Lambda -- Summary of the Proof of Theorem 10.2.4(a) -- Proof of Theorem 10.2.4(b) -- 10.2.4. Constructive Recognition: The Case of Giants -- 10.3. A Randomized Strong Generator Construction -- Bibliography -- Index.
Summary: Theory of permutation group algorithms for graduates and above. Exercises and hints for implementation throughout.
Holdings
Item type Current library Call number Status Date due Barcode Item holds
Ebrary Ebrary Afghanistan
Available EBKAF0006584
Ebrary Ebrary Algeria
Available
Ebrary Ebrary Cyprus
Available
Ebrary Ebrary Egypt
Available
Ebrary Ebrary Libya
Available
Ebrary Ebrary Morocco
Available
Ebrary Ebrary Nepal
Available EBKNP0006584
Ebrary Ebrary Sudan

Access a wide range of magazines and books using Pressreader and Ebook central.

Enjoy your reading, British Council Sudan.

Available
Ebrary Ebrary Tunisia
Available
Total holds: 0

Cover -- Half-title -- Title -- Copyright -- Contents -- 1 Introduction -- Acknowledgments -- 1.1. List of Algorithms -- 1.2. Notation and Terminology -- 1.2.1. Groups -- 1.2.2. Permutation Groups -- 1.2.3. Algorithmic Concepts -- 1.2.4. Graphs -- 1.3.Classification of Randomized Algorithms -- 2 Black-Box Groups -- 2.1. Closure Algorithms -- 2.1.1. Orbit Computations -- 2.1.2.Closure of Algebraic Structures -- The Closure Algorithm -- Algorithms Based on Normal Closure -- 2.2. Random Elements of Black-Box Groups -- The Product Replacement Algorithm -- 2.3. Random Subproducts -- 2.3.1. Definition and Basic Properties -- 2.3.2. Reducing the Number of Generators -- 2.3.3. Closure Algorithms without Membership Testing -- 2.3.4. Derived and Lower Central Series -- 2.4. Random Prefixes -- 2.4.1. Definition and Basic Properties -- 2.4.2. Applications -- Exercises -- 3 Permutation Groups A Complexity Overview -- 3.1. Polynomial-Time Algorithms -- 3.2. Nearly Linear-Time Algorithms -- 3.3. Non-Polynomial-Time Methods -- 4 Bases and Strong Generating Sets -- 4.1. Basic Definitions -- The Sifting Procedure -- 4.2. The Schreier-Sims Algorithm -- The Schreier-Sims Algorithm -- 4.3. The Power of Randomization -- The Random Schreier-Sims Algorithm -- 4.4. Shallow Schreier Trees -- 4.5. Strong Generators in Nearly Linear Time -- The SGS Construction -- The Algorithm Solving (4.6) -- 4.5.1. Implementation -- Exercises -- 5 Further Low-Level Algorithms -- 5.1. Consequences of the Schreier-Sims Method -- 5.1.1. Pointwise Stabilizers -- 5.1.2. Homomorphisms -- 5.1.3. Transitive Constituent and Block Homomorphisms -- The Block Homomorphism Algorithm -- 5.1.4. Closures and Normal Closures -- 5.2. Working with Base Images -- 5.3. Permutation Groups as Black-Box Groups -- Representation as a Black-Box Group -- 5.4. Base Change.

The Exchange of Two Base Points (Deterministic Version) -- The Exchange of Two Base Points (Las Vegas Version) -- Base Change by Conjugation -- 5.5. Blocks of Imprimitivity -- 5.5.1. Blocks in Nearly Linear Time -- 5.5.2. The Smallest Block Containing a Given Subset -- Computation of the Smallest Block Containing… -- 5.5.3. Structure Forests -- Exercises -- 6 A Library of Nearly Linear-Time Algorithms -- 6.1. Special Case of Group Intersection and pplications -- 6.1.1. Intersection with a Normal Closure -- 6.1.2. Centralizer in the Symmetric Group -- 6.1.3. The Center -- 6.1.4. Centralizer of a Normal Subgroup -- 6.1.5. Core of a Subnormal Subgroup -- 6.2. Composition Series -- 6.2.1. Reduction to the Primitive Case -- 6.2.2. The O'Nan-Scott Theorem -- 6.2.3. Normal Subgroups with Nontrivial Centralizer -- Computing the Socle of a Frobenius Group -- Luks's Algorithm -- Neumann's Algorithm (the EARNS Subroutine) -- 6.2.4. Groups with a Unique Nonabelian Minimal Normal Subgroup -- The Algorithm for Case B of Theorem 6.2.7 -- The Algorithm for Case C(i) -- The Algorithm for Case C(ii) -- The Algorithm for Case C(iii) -- 6.2.5. Implementation -- 6.2.6. An Elementary Version -- Beals's Algorithm for Groups with Regular Normal Subgroups -- Beals's Algorithm for Groups with No Regular Normal Subgroups -- 6.2.7. Chief Series -- 6.3. Quotients with Small Permutation Degree -- 6.3.1. Solvable Radical and p-Core -- The Algorithms -- Exercises -- 7 Solvable Permutation Groups -- 7.1. Strong Generators in Solvable Groups -- The Generalized Normal Closure Algorithm -- 7.2. Power-Conjugate Presentations -- Conversion to a pcp -- 7.3. Working with Elementary Abelian Layers -- 7.3.1. Sylow Subgroups -- 7.3.2. Conjugacy Classes in Solvable Groups -- Computation of the Class Representatives -- Computation of the Centralizers -- 7.4. Two Algorithms for Nilpotent Groups.

7.4.1. A Fast Nilpotency Test -- 7.4.2. The Upper Central Series in Nilpotent Groups -- Exercises -- 8 Strong Generating Tests -- 8.1. The Schreier-Todd-Coxeter-Sims Procedure -- 8.1.1. Coset Enumeration -- 8.1.2. Leon's Algorithm -- The STCS Algorithm -- 8.2. Sims's Verify Routine -- The Verify Routine -- 8.3. Toward Strong Generators by a Las Vegas Algorithm -- 8.4. Short Presentation -- 9 Backtrack Methods -- 9.1. Traditional Backtrack -- 9.1.1. Pruning the Search Tree: Problem-Independent Methods -- 9.1.2. Pruning the Search Tree: Problem-Dependent Methods -- 9.2. The Partition Method -- 9.3. Normalizers -- 9.4. Conjugacy Classes -- Class Representatives by Random Sampling -- Representatives in Centralizers of p-Elements -- Separation of the Solvable Radical -- Exercises -- 10 Large-Base Groups -- 10.1. Labeled Branchings -- 10.1.1. Construction -- 10.2. Alternating and Symmetric Groups -- 10.2.1. Number Theoretic and Probabilistic Estimates -- 10.2.2. Constructive Recognition: Finding the New Generators -- 10.2.3. Constructive Recognition: The Homomorphism Lambda -- Summary of the Proof of Theorem 10.2.4(a) -- Proof of Theorem 10.2.4(b) -- 10.2.4. Constructive Recognition: The Case of Giants -- 10.3. A Randomized Strong Generator Construction -- Bibliography -- Index.

Theory of permutation group algorithms for graduates and above. Exercises and hints for implementation throughout.

Description based on publisher supplied metadata and other sources.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2019. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.

There are no comments on this title.

to post a comment.