libsemigroups - Version 2.5.1
C++ library for semigroups and monoids
libsemigroups is a C++14 library containing implementations of several
algorithms for computing finite, and finitely presented, semigroups and
- 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
- 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 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
available on github, and some related projects are here.
The main classes in
libsemigroups are named after the algorithms they
implement; see, for example,
The implementations in
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 documentation https://libsemigroups.readthedocs.io/en/latest/
Installation instructions are here https://libsemigroups.readthedocs.io/en/latest/install.html
If you find any problems with
libsemigroups, or have any suggestions for
features that you'd like to see, please use the issue tracker.
- Reinis Cirpons (email@example.com) contributed to
IsObviouslyInfinite, to integrating
eigen, and contributed an implementation of the Radoszewski-Rytter algorithm for testing equivalence of words in free bands.
- Joseph Edwards (firstname.lastname@example.org) contributed the container
- Luke Elliott (email@example.com) contributed to the Schreier-Sims implementation.
- Jan Engelhardt (firstname.lastname@example.org) contributed some bug fixes to the build system, and a number of helpful issues.
- Ilya Finkelshteyn (email@example.com) contributed to the continuous integration in AppVeyor.
- Isuru Fernando (firstname.lastname@example.org) contributed to the build system.
- Florent Hivert (Florent.Hivert@lri.fr) contributed many helpful ideas to
libsemigroups, an allocator implementation (to be included in a future version), and
- Max Horn (email@example.com) contributed some fixes.
- Jerry James (firstname.lastname@example.org) contributed some bugfixes.
- Julius Jonušas contributed to the implementation of the Froidure-Pin algorithm.
- Alex Levine contributed to the Schreier-Sims implementation.
- Dima Pasechnik (email@example.com) contributed to the build system.
- Chris Russell contributed some tests for finitely presented semigroups.
- Finn Smith (firstname.lastname@example.org) contributed the implementation of the Konieczny and Lallement-McFadden algorithm, to the Todd-Coxeter implementation, and to BMat8s.
- Nicolas Thiéry (email@example.com) contributed to the build system,
libsemigroupsvia conda, the python bindings and many helpful conversations and suggestions.
- Maria Tsalakou (firstname.lastname@example.org) contributed to the Knuth-Bendix
implementation, related algorithms for the class
ActionDigraph, and to the implementation of the
- Wilf Wilson (email@example.com) contributed some fixes.
- Murray Whyte (firstname.lastname@example.org) contributed to the documentation and reported a number of bugs.
- Michael Young (email@example.com) contributed to the congruences code in the v0.0.1 to v0.6.7.
We acknowledge financial support from the OpenDreamKit Horizon 2020 European Research Infrastructures project (#676541) (primarily for the python bindings).
We thank the Engineering and Physical Sciences Research Council (EPSRC) for funding the PhD scholarships of Michael Young and Finn Smith when they worked on this project (EP/M506631/1, EP/N509759/1).