Julia bindings for the libsemigroups C++ library.
What is libsemigroups?
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(url="https://github.com/libsemigroups/Semigroups.jl")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:
| Command | Description |
|---|---|
make test |
Run the test suite |
make docs |
Build documentation |
make docs-serve |
Build and serve docs locally |
make build |
Build C++ bindings |
make clean |
Clean build artifacts |
make format |
Format Julia and C++ code |