What is libsemigroups?

Before explaining what libsmigroups_pybind11 is, it is first necessary to explain libsemigroups. libsemigroups is a C++17 library containing implementations of several algorithms for computing finite, and finitely presented, semigroups and monoids. The main algorithms implemented in libsemigroups are:

• the Froidure-Pin algorithm for computing semigroups and monoids defined by a generating set consisting of elements whose multiplication and equality is decidable (such as transformations, partial permutations, permutations, bipartitions, and matrices over a semiring);

• Kambites’ algorithm for solving the word problem in small overlap monoids from Small overlap monoids I: The word problem, and the algorithm from An explicit algorithm for normal forms in small overlap monoids;

• the Knuth-Bendix algorithm for finitely presented semigroups and monoids; a version of Sims’ low index subgroup algorithm for computing congruences of a semigroup or monoid from Computing finite index congruences of finitely presented semigroups and monoids in the classes;

• a generalized version of the algorithms described in Green’s equivalences in finite semigroups of binary relations by Konieczny, and On the determination of Green’s relations in finite transformation semigroups by Lallement and Mcfadden for computing finite semigroups and monoids admitting a pair of actions with particular properties;

• the algorithm from Efficient Testing of Equivalence of Words in a Free Idempotent Semigroup by Radoszewski and Rytter;

• a non-random version of the Schreier-Sims algorithm for permutation groups;

• a version of Stephen’s procedure from Applications of automata theory to presentations of monoids and inverse monoids for finitely presented inverse semigroups and monoids (for a given word w this procedure is for determining words equivalent to w or that are left divisors of w);

• the Todd-Coxeter algorithm for finitely presented semigroups and monoids; see also The Todd-Coxeter algorithm for semigroups and monoids.

libsemigroups is partly based on Algorithms for computing finite semigroups, Expository Slides, and Semigroupe 2.01 by Jean-Eric Pin.

What is libsemigroups_pybind11?

libsemigroups_pybind11 is a package for Python 3.9+ exposing much (but not all) of the functionality of libsemigroups. It is built with the help of the excellent library pybind11, for which we are very grateful. A more detailed description of the structure of this package, along with some associated quirks, is described on the exceptions page.

The development version of libsemigroups_pybind11 is available on github, and some related projects are here.

How to install libsemigroups_pybind11

To see the different ways libsemigroups_pybind11 can be installed, see the installation page.

Issues

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

Acknowledgements

In addition to libsemigroups, there are several excellent projects that are utilised in the development of libsemigroups_pybind11, specifically:

• codespell, cpplint, Pylint and Ruff for code quality;

• Graphviz for graph visualisation;

• pybind11 for assistance in the binding of libsemigroups;

• pytest for testing; and

• Sphinx for the documentation.

We would like to thank the authors and contributors of these projects!