Finitely Presented Groups

It follows from the well known theorems on the algorithmic unsolvability of the word problem and related problems that there are no deterministic methods to answer most questions about the structure of finitely presented groups. For these essentially two approaches are possible: On one hand trial-and-error methods such as the Todd-Coxeter and Knuth-Bendix methods, on the other hand methods to find certain factor groups of described structure, most of which are based on the idea of ‘collection’. For theoretical background of the implemented methods see the book “Computation with finitely presented groups” of Charles Sims.

The main GAP library provides methods for handling finitely presented groups such as

• Todd-Coxeter,
• Reidemeister-Schreier,
• Low Index Subgroups, as well as
• certain quotient methods.

Also there are functions to handle Tietze transformations.

In addition there are packages

• FGA providing algorithms for free groups,
• ACE linking to a particular powerful implementation of the Todd-Coxeter method,
• ITC providing an interactive Todd-Coxeter mainly for teaching and learning,
• ANUPQ for finding p-quotients, standard presentations, and descendants,
• NQ for finding infinite nilpotent quotients, and
• KBMAG with Knuth-Bendix and automatic groups methods.