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 ([email protected])

Contributors

• Reinis Cirpons ([email protected]) 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 ([email protected]) contributed the container StaticTriVector2.
• Luke Elliot ([email protected]) - contributed to the Schreier-Sims implementation.
• Ilya Finkelshteyn ([email protected]) contributed to the continuous integration in AppVeyor.
• Isuru Fernando ([email protected]) contributed to the build system.
• Florent Hivert ([email protected]) contributed many helpful ideas to libsemigroups, an allocator implementation (to be included in a future version), and HPCombi.
• Max Horn ([email protected]) contributed some fixes.
• Jerry James ([email protected]) 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 protected]) contributed to the build system.
• Chris Russell contributed some tests for finitely presented semigroups.
• Finn Smith ([email protected]) contributed the implementation of the Konieczny and Lallement-McFadden algorithm, to the Todd-Coxeter implementation, and to BMat8s.
• Nicolas Thiéry ([email protected]) contributed to the build system, packaging libsemigroups via conda, the python bindings and many helpful conversations and suggestions.
• Maria Tsalakou ([email protected]) 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 ([email protected]) contributed some fixes.
• `Murray Whyte`_ ([email protected]) contributed to the documentation and reported a number of bugs.
• Michael Young ([email protected]) 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).