# libsemigroups - Version 2.0.0¶

## 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.
Namely:

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

the Todd-Coxeter algorithm for finitely presented semigroups and monoids;

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].

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::KnuthBendix`

, and
`libsemigroups::SchreierSims`

.

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.

### How to use it¶

See the installation instructions:

`libsemigroups`

is used in the Semigroups package for GAP, and the
development version is available on github. There were python bindings
(for Python 2 and 3) for earlier versions of `libsemigroups`

, and there will
be in the future too, but presently they don’t work.

For the authors, contributors, and acknowledgements and a comparison with Semigroupe by Jean-Eric Pin see below.