libsemigroups

What is 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) in the libsemigroups::FroidurePin class template;
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" in the class template libsemigroups::Kambites;
the Knuth-Bendix algorithm for finitely presented semigroups and monoids in the class template libsemigroups::KnuthBendix;
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 libsemigroups::Sims1 and libsemigroups::Sims2;
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, in the class template libsemigroups::Konieczny;
the algorithm from "Efficient Testing of Equivalence of Words in a Free Idempotent Semigroup" by Radoszewski and Rytter in the function libsemigroups::freeband_equal_to;
a non-random version of the Schreier-Sims algorithm for permutation groups in the class template libsemigroups::SchreierSims;
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\)) in the class template libsemigroups::Stephen;
the Todd-Coxeter algorithm for finitely presented semigroups and monoids; in the class template libsemigroups::ToddCoxeter; 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.

libsemigroups is used in the Semigroups package for GAP (see [45]), 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.

Design principles

The main classes in libsemigroups are named after the algorithms they implement; see, for example, libsemigroups::FroidurePin, libsemigroups::Konieczny, libsemigroups::ToddCoxeter, libsemigroups::Kambites, libsemigroups::KnuthBendix, libsemigroups::SchreierSims, libsemigroups::Sims1, libsemigroups::Sims2, or libsemigroups::Stephen.

libsemigroups is a modern open source C++ library designed to be:

state of the art: the mathematical underpinnings of several of the algorithms in libsemigroups originate from the authors and contributors; and the other algorithms are adapted from the literature (see above for details);
extensible: libsemigroups::FroidurePin, libsemigroups::Konieczny, and libsemigroups::SchreierSims are generic and can be adapted to user-defined types;
adaptable: the behaviour of many algorithms implementing in libsemigroups can be fine-tuned via many settings, and used interactively via the functions libsemigroups::Runner::run_for and libsemigroups::Runner::run_until;
easy to use: converting between different types of libsemigroups objects (see the to function) is easy; there are many helper functions to streamline common tasks; high quality exception messages are implemented throughout the code base (although you don't have to use these if you don't want to); long running algorithms can provide detailed feedback on their progress (see libsemigroups::ReportGuard); many data structures can be visualised using graphviz (see libsemigroups::Dot and Visualisation); and there are hundreds of examples in the tests directory.
fast: libsemigroups is designed with performance in mind; several classes implement parallel algorithms (libsemigroups::Sims1, libsemigroups::Sims2, libsemigroups::Congruence); we provide some "winner takes all" mechanisms for running algorithms concurrently (see libsemigroups::Congruence); there are _no_checks versions of most functions if performance is critical.

How to use libsemigroups

See the documentation https://libsemigroups.github.io/libsemigroups/.

Installation

See the installation page for more info.

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.

Dependencies

libsemigroups uses:

Catch2 for tests and benchmarks;
eigen for some linear algebra computations [28];
fmt for string formatting;
HPCombi which uses the SSE and AVX instruction sets for very fast manipulation of transformations, partial permutations, permutations, and boolean matrices of small size;
backward-cpp for beautiful backtraces;
magic_enum for static reflection for enums;
rx-ranges the minimalist ranges library for C++17.

We'd like to thank the authors and contributors to these excellent projects!

Authors

Contributors

Luna Elliott (luna..nosp@m.elli.nosp@m.ott14.nosp@m.2857.nosp@m.@gmai.nosp@m.l.co.nosp@m.m) contributed to the Schreier-Sims implementation.
Jan Engelhardt (jenge.nosp@m.lh@i.nosp@m.nai.d.nosp@m.e) contributed some bug fixes to the build system, and a number of helpful issues.
Ilya Finkelshteyn (ilyaf.nosp@m.@app.nosp@m.veyor.nosp@m..com) contributed to the continuous integration in AppVeyor.
Isuru Fernando (isuru.nosp@m.f@gm.nosp@m.ail.c.nosp@m.om) contributed to the build system.
Florent Hivert (Flore.nosp@m.nt.H.nosp@m.ivert.nosp@m.@lri.nosp@m..fr) contributed many helpful ideas to libsemigroups, and HPCombi.
Max Horn (max@q.nosp@m.uend.nosp@m.i.de) contributed some fixes.
Jerry James (logan.nosp@m.jerr.nosp@m.y@gma.nosp@m.il.c.nosp@m.om) contributed some bugfixes.
Julius Jonušas contributed to the implementation of the Froidure-Pin algorithm.
Samuel Lelièvre (samue.nosp@m.l.le.nosp@m.lievr.nosp@m.e@gm.nosp@m.ail.c.nosp@m.om) contributed a number of fixes to the docs.
Alex Levine (A.Lev.nosp@m.ine@.nosp@m.uea.a.nosp@m.c.uk) contributed to the Schreier-Sims implementation.
Michael Orlitzky (micha.nosp@m.el@o.nosp@m.rlitz.nosp@m.ky.c.nosp@m.om) contributed to the build system.
Dima Pasechnik (dimpa.nosp@m.se@g.nosp@m.mail..nosp@m.com) contributed to the build system.
Chris Russell contributed some tests for finitely presented semigroups.
Finn Smith (fls3@.nosp@m.st-a.nosp@m.ndrew.nosp@m.s.ac.nosp@m..uk) contributed the implementation of the Konieczny and Lallement-McFadden algorithm, to the Todd-Coxeter implementation, and to BMat8s.
Nicolas Thiéry (nthie.nosp@m.ry@u.nosp@m.sers..nosp@m.sf.n.nosp@m.et) contributed to the build system, packaging libsemigroups via conda, the python bindings and many helpful conversations and suggestions.
Maria Tsalakou (mt200.nosp@m.@st-.nosp@m.andre.nosp@m.ws.a.nosp@m.c.uk) contributed to the Knuth-Bendix implementation, related algorithms for the class WordGraph, and to the implementation of the Ukkonen and Kambites classes.
Wilf Wilson (wilf@.nosp@m.wilf.nosp@m.-wils.nosp@m.on.n.nosp@m.et) contributed some fixes.
Murray Whyte (mw231.nosp@m.@st-.nosp@m.andre.nosp@m.ws.a.nosp@m.c.uk) contributed many examples of finitely presented semigroups and monoids, to the documentation and reported a number of bugs.
Michael Young (mct25.nosp@m.@st-.nosp@m.andre.nosp@m.ws.a.nosp@m.c.uk) contributed to the congruences code in the v0.0.1 to v0.6.7.

Acknowledgements

We thank:

OpenDreamKit Horizon 2020 European Research Infrastructures project (#676541);
the Carnegie Trust for the Universities of Scotland for funding the PhD scholarship of Julius Jonušas;
the EPSRC for funding the PhD scholarships of Michael Young, Finn Smith, and Reinis Cirpons (EP/M506631/1, EP/N509759/1 and EP/V520123/1);
the School of Mathematics and Statistics, University of St Andrews for funding the PhD scholarships of Maria Tsalakou, Joseph Edwards, and Murray Whyte;
the Cyprus State Scholarship Foundation for their financial support for Maria Tsalakou.