libsemigroups - Version 2.2.2

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.

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, or libsemigroups::Sims1.

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.

Installation and changelog

• Installation
• Changelog - version 2
• Changelog - version 1

API REFERENCE

• Actions
• Congruences
• Digraphs
• Elements
• Finitely presented semigroups
• Free Bands
• Matrix
• Miscellaneous
• Orders
• Semigroups
• Words

Bibliography

• Bibliography

Further info

• Semigroupe
• Authors