Julia bindings for the libsemigroups C++ library.

Before explaining what Semigroups.jl 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";
• 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;
• 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.

Semigroups.jl is a package for Julia 1.9+ exposing much (but not all) of the functionality of libsemigroups. It is built with the help of the excellent library CxxWrap.jl, for which we are very grateful.

The development version of Semigroups.jl is available on GitHub, and some related projects are here.

To install Semigroups.jl from GitHub:

using Pkg
Pkg.add("Semigroups")
using Semigroups

For more detailed installation instructions, including prerequisites and troubleshooting, see the documentation.

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

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

• CxxWrap.jl for Julia-C++ interop;
• Documenter.jl for the documentation.

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

A Makefile is provided for common development tasks: