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;
• the Todd-Coxeter algorithm for finitely presented semigroups and monoids; see also this paper;
• the Knuth-Bendix algorithm for finitely presented semigroups and monoids;
• the Schreier-Sims algorithm for permutation groups;
• a preliminary implementation of the Konieczny and Lallement-McFadden algorithm for computing finite semigroups which act on sets;
• an implementation of the Radoszewski-Rytter 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, Kambites, and Mitchell-Tsalakou.

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