Computation with Finitely Presented GroupsResearch in computational group theory, an active subfield of computational algebra, has emphasised three areas: finite permutation groups, finite solvable groups, and finitely presented groups. This book deals with the third of these areas. The author emphasises the connections with fundamental algorithms from theoretical computer science, particularly the theory of automata and formal languages, computational number theory, and computational commutative algebra. The LLL lattice reduction algorithm and various algorithms for Hermite and Smith normal forms from computational number theory are used to study the abelian quotients of a finitely presented group. The work of Baumslag, Cannonito and Miller on computing nonabelian polycyclic quotients is described as a generalisation of Buchberger's Gröbner basis methods to right ideals in the integral group ring of a polycyclic group. Researchers in computational group theory, mathematicians interested in finitely presented groups and theoretical computer scientists will find this book useful. |
Contents
Introduction | 1 |
1 Basic concepts | 6 |
2 Rewriting systems | 43 |
3 Automata and rational languages | 96 |
4 Subgroups of free products of cyclic groups | 151 |
5 Coset enumeration | 217 |
6 The ReidemeisterSchreier procedure | 268 |
7 Generalized automata | 296 |
8 Abelian groups | 319 |
9 Polycyclic groups | 383 |
10 Module bases | 448 |
11 Quotient groups | 514 |
Implementation issues | 570 |
| 581 | |
| 597 | |
Other editions - View all
Common terms and phrases
A₁ abelian group algorithm assume automata b₁ b₂ begin Let column compute congruence consistent construct contains corner entries Corollary coset automaton coset enumeration coset table cyclic groups defined denote described deterministic E₁ elements End End equivalent Example Exercise finite set finitely presented groups free abelian group free group given Gröbner basis group G H₁ Hermite normal form homomorphism Input integer matrix isomorphic Knuth-Bendix procedure labels left side Lemma length-plus-lexicographic ordering Let G M₁ modulo monoid monomials N₁ niladic nilpotent nonempty nonzero normal subgroup Overlap pairs path permutation polycyclic groups polycyclic presentation polynomials positive integer prefix Proof Proposition quotient reduced reduction ordering relations respect row Hermite normal rules S₁ Section sequence Sg(P Smith normal form stack standard strategy subgroup of G submodule subword Suppose trivial two-sided trace u₁ V₁ vector W₁ word