# libsemigroups

[libsemigroups](https://libsemigroups.readthedocs.io/) is a C++14 library

containing implementations of several algorithms for computing finite, and

finitely presented, semigroups and monoids. Namely:

- the [Froidure-Pin algorithm](https://www.irif.fr/~jep/PDF/Rio.pdf) for

  computing finite semigroups;

- the [Todd-Coxeter algorithm](https://en.wikipedia.org/wiki/Todd%E2%80%93Coxeter_algorithm)

  for finitely presented semigroups and monoids; see also

  [this paper](https://arxiv.org/abs/2203.11148);

- the [Knuth-Bendix algorithm](https://en.wikipedia.org/wiki/Knuth%E2%80%93Bendix_completion_algorithm)

  for finitely presented semigroups and monoids;

- the [Schreier-Sims algorithm](https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm)

  for permutation groups;

- a preliminary implementation of the

  [Konieczny](https://link.springer.com/article/10.1007/BF02573672) and

  [Lallement-McFadden](https://www.sciencedirect.com/science/article/pii/S0747717108800570)

  algorithm for computing finite semigroups which act on sets;

- an implementation of the

  [Radoszewski-Rytter](https://link.springer.com/chapter/10.1007/978-3-642-11266-9_55)

  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](https://doi.org/10.1016/j.jalgebra.2008.09.038),

  [Kambites](https://doi.org/10.1016/j.jalgebra.2008.12.028), and

  [Mitchell-Tsalakou](http://arxiv.org/abs/2105.12125).

Libsemigroups is partly based on

["Algorithms for computing finite semigroups"](https://www.irif.fr/~jep/PDF/Rio.pdf),

["Expository Slides"](https://www.irif.fr/~jep/PDF/Exposes/StAndrews.pdf), and

[Semigroupe 2.01](https://www.irif.fr/~jep/Logiciels/Semigroupe2.0/semigroupe2.html)

by [Jean-Eric Pin](https://www.irif.fr/~jep/).

Libsemigroups is used in the

[Semigroups package](https://semigroups.github.io/Semigroups/) for

[GAP](https://www.gap-system.org/), 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](https://github.com/libsemigroups/libsemigroups), and some related

projects are [here](https://github.com/libsemigroups).

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`, 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](https://github.com/hivert/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](https://github.com/catchorg/Catch2) for tests;

[fmt](https://github.com/fmtlib/fmt) for reporting; and

[eigen](http://eigen.tuxfamily.org/) for some linear algebra computations.