libsemigroups - Version 2.0.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. 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:

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

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.

API REFERENCE

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

Bibliography

• Bibliography

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

Further info

• Semigroupe
• Authors