# libsemigroups - Version 2.5.1¶

## C++ library for semigroups and monoids¶

### What is `libsemigroups`

?¶

`libsemigroups`

is a C++14 library containing implementations of several
algorithms for computing finite, and finitely presented, semigroups and
monoids. Namely:

the Froidure-Pin algorithm for computing finite semigroups [FP97];

the Todd-Coxeter algorithm for finitely presented semigroups and monoids; see also this paper [CMST22];

the Knuth-Bendix algorithm for finitely presented semigroups and monoids;

the Schreier-Sims algorithm for permutation groups;

a preliminary implementation of the Konieczny [Kon94] and Lallement-McFadden [LM90] algorithm for computing finite semigroups which act on sets;

an implementation of the Radoszewski-Rytter [RR10] algorithm for testing equivalence of words in free bands;

an implementation of the algorithm for solving the word problem for small overlap monoids, and for computing normal forms in such monoids; see Kambites [Kam09b], Kambites [Kam09a], and Mitchell-Tsalakou [MT21];

a version of Sims low index subgroup algorithm for computing one-sided congruences of a semigroup or monoid;

a version of Stephen’s procedure for finitely presented semigroups and monoids (for a given word \(w\) this procedure is for determining words equivalent to \(w\) or that are left divisors of \(w\)).

`libsemigroups`

is partly based on Algorithms for computing finite
semigroups, Expository Slides, and Semigroupe 2.01 by Jean-Eric Pin.

`libsemigroups`

is used in the Semigroups package for GAP, and it is
possible to use `libsemigroups`

directly in Python 3 via the package
libsemigroups_pybind11. The development version of `libsemigroups`

is
available on github, and some related projects are here.

The main classes in `libsemigroups`

are named after the algorithms they
implement; see, for example, `libsemigroups::FroidurePin`

,
`libsemigroups::Konieczny`

,
`libsemigroups::congruence::ToddCoxeter`

,
`libsemigroups::fpsemigroup::Kambites`

,
`libsemigroups::fpsemigroup::KnuthBendix`

,
`libsemigroups::SchreierSims`

,
`libsemigroups::Sims1`

, or
`libsemigroups::Stephen`

.

The implementations in `libsemigroups::FroidurePin`

,
`libsemigroups::Konieczny`

, and `libsemigroups::SchreierSims`

are generic and easily adapted to user-defined types.

`libsemigroups`

uses: HPCombi which uses the SSE and AVX instruction sets
for very fast manipulation of transformations, partial permutations,
permutations, and boolean matrices of small size; catch for tests;
fmt for reporting; and eigen for some linear algebra computations.