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;
• 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.

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.

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

Issues

If you find any problems with libsemigroups, or have any suggestions for features that you'd like to see, please use the issue tracker.

Author

James Mitchell (jdm3@st-andrews.ac.uk)

Contributors

• Reinis Cirpons (rc234@st-andrews.ac.uk) 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 (jde1@st-andrews.ac.uk) contributed the container StaticTriVector2.
• Luke Elliot (le27@st-andrews.ac.uk) - contributed to the Schreier-Sims implementation.
• Ilya Finkelshteyn (ilyaf@appveyor.com) contributed to the continuous integration in AppVeyor.
• Isuru Fernando (isuruf@gmail.com) 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 HPCombi.
• Max Horn (max@quendi.de) contributed some fixes.
• Jerry James (loganjerry@gmail.com) 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 (dimpase@gmail.com) contributed to the build system.
• Chris Russell contributed some tests for finitely presented semigroups.
• Finn Smith (fls3@st-andrews.ac.uk) contributed the implementation of the Konieczny and Lallement-McFadden algorithm, to the Todd-Coxeter implementation, and to BMat8s.
• Nicolas Thiéry (nthiery@users.sf.net) contributed to the build system, packaging libsemigroups via conda, the python bindings and many helpful conversations and suggestions.
• Maria Tsalakou (mt200@st-andrews.ac.uk) contributed to the Knuth-Bendix implementation, related algorithms for the class :cpp:any:`ActionDigraph`, and to the implementation of the :cpp:any:`Kambites` class.
• Wilf Wilson (wilf@wilf-wilson.net) contributed some fixes.
• `Murray Whyte`_ (mw231@st-andrews.ac.uk) contributed to the documentation and reported a number of bugs.
• Michael Young (mct25@st-andrews.ac.uk) contributed to the congruences code in the v0.0.1 to v0.6.7.

Acknowledgements

We acknowledge financial support from the OpenDreamKit Horizon 2020 European Research Infrastructures project (#676541) (primarily for the python bindings).

We thank the Carnegie Trust for the Universities of Scotland for funding the PhD scholarship of `J. Jonušas`_ when he worked on this project.

We thank the Engineering and Physical Sciences Research Council (EPSRC) for funding the PhD scholarships of `M. Torpey`_ and `F. Smith`_ when they worked on this project (EP/M506631/1, EP/N509759/1).