libsemigroups - Version 2.7.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 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;
a version of Stephen’s procedure for finitely presented semigroups and monoids (for a given word \(w\) this procedure is for determining words equivalent to \(w\) or that are left divisors of \(w\)).
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,
libsemigroups::Sims1, or
libsemigroups::Stephen.
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
API REFERENCE
Bibliography
Further info