About C/C++ GAP Python Julia Return To Top

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;
  • Kambites’ algorithm for solving the word problem in small overlap monoids, and the algorithm for computing normal forms for small overlap monoids by the authors of libsemigroups;
  • 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;
  • a generalized version of Konieczny’s and Lallement and Mcfadden’s algorithms;
  • Radoszewski and Rytter’s algorithm from testing equality of words in free bands;
  • a non-random version of the Schreier-Sims algorithm;
  • a version of Stephen’s procedure from for finitely presented inverse semigroups and monoids;
  • the Todd-Coxeter algorithm for finitely presented semigroups and monoids.

C/C++

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

  • state of the art: the mathematical underpinnings of the algorithms in libsemigroups use the current state of the art;
  • extensible: several of the implementations in libsemigroups are generic and easily adaptable to user-defined types;
  • adaptable: the behaviour the algorithms implemented in libsemigroups can be fine-tuned via many settings, and used interactively via the functions;
  • easy to use: converting between different types of libsemigroups objects 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; many data structures can be visualised; and there are hundreds of examples.
  • fast: libsemigroups is designed with performance in mind; several classes implement parallel algorithms; we provide some “winner takes all” mechanisms for running algorithms concurrently; and there are _no_checks versions of most functions if performance is critical.

GAP

libsemigroups is the workhorse of the GAP package Semigroups performing fundamental computations for finite and fintely presented semigroups and monoids. Many of these beat the corresponding methods in the GAP library, despite libsemigroups not having any optimisations specific to groups.

F := FreeGroup(11);;
R := [];;
for i in [1 .. 11] do
  Add(R, [F.(i) ^ 2, One(F)]);
od;
for i in [1 .. 10] do
  Add(R, [F.(i) * F.(i + 1) * F.(i), F.(i + 1) * F.(i) * F.(i + 1)]);
od;
for i in [1 .. 9] do
  for j in [i + 2 .. 11] do
    Add(R, [F.(i) * F.(j), F.(j) * F.(i)]);
  od;
od;
G := F / R;
Size(G); # runs forever

But with the Semigroups package loaded:

F := FreeMonoid(11);;
R := [];;
for i in [1 .. 11] do
  Add(R, [F.(i) ^ 2, One(F)]);
od;
for i in [1 .. 10] do
  Add(R, [F.(i) * F.(i + 1) * F.(i), F.(i + 1) * F.(i) * F.(i + 1)]);
od;
for i in [1 .. 9] do
  for j in [i + 2 .. 11] do
    Add(R, [F.(i) * F.(j), F.(j) * F.(i)]);
  od;
od;
G := F / R;
Size(G);  # 479001600
time; # 60

Python

libsemigroups is available to use directly in Python via the package libsemigroups_pybind11. Repeating the example in the GAP section above:

from libsemigroups_pybind11 import KnuthBendix, congruence_kind
from libsemigroups_pybind11.presentation import examples
p = examples.symmetric_group_Moo97_a(12)
kb = KnuthBendix(congruence_kind.twosided, p)
kb.number_of_classes() # returns math.factorial(12)

Almost every feature of libsemigroups is available in libsemigroups_pybind11.