Two variants of the Froiduire-Pin Algorithm for finite semigroups
J. Jonušas, J. D. Mitchell, and M. Pfeiffer
June 12, 2017

arXiv:1704.04084v2 [math.GR] 9 Jun 2017

Abstract
In this paper, we present two algorithms based on the Froidure-Pin Algorithm for computing the
structure of a finite semigroup from a generating set. As was the case with the original algorithm of
Froidure and Pin, the algorithms presented here produce the left and right Cayley graphs, a confluent
terminating rewriting system, and a reduced word of the rewriting system for every element of the
semigroup.
If U is any semigroup, and A is a subset of U , then we denote by hAi the least subsemigroup
of U containing A. If B is any other subset of U , then, roughly speaking, the first algorithm we
present describes how to use any information about hAi, that has been found using the Froidure-Pin
Algorithm, to compute the semigroup hA ∪ Bi. More precisely, we describe the data structure for a
finite semigroup S given by Froidure and Pin, and how to obtain such a data structure for hA∪Bi from
that for hAi. The second algorithm is a lock-free concurrent version of the Froidure-Pin Algorithm.

1

Introduction

A semigroup is just a set U together with an associative binary operation. If A is a subset of a semigroup
U , then we denote by hAi the smallest subsemigroup of U containing A, and refer to A as the generators of
hAi. If A and B are subsets of U , then we write hA, Bi rather than hA ∪ Bi. The question of determining
the structure of the semigroup hAi given the set of generators A has a relatively long history; see the
introductions of [2] or [4] for more details.
In [4] the authors present an algorithm for computing a finite semigroup; we refer to this as the
Froidure-Pin Algorithm. More precisely, given a set A of generators belonging to a larger semigroup U ,
the Froidure-Pin Algorithm simultaneously enumerates the elements, produces the left and right Cayley
graphs, a confluent terminating rewriting system, and a reduced word of the rewriting system for every
element of hAi. The Froidure-Pin Algorithm is perhaps the first algorithm for computing an arbitrary finite
semigroup and is still one of the most powerful, at least for certain types of semigroup. Earlier algorithms,
such as those in [8,9], often only applied to specific semigroups, such as those of transformations or Boolean
matrices. In contrast, the Froidure-Pin Algorithm can be applied to any semigroup where it is possible to
multiply and test equality of the elements.
Green’s relations are one of the most fundamental aspects of the structure of a semigroup, from both
a theoretical and a practical perspective; see [7] or [18] for more details. The Green’s structure of a
semigroup underlies almost every other structural feature. As such determining the Green’s relations
of a finite semigroup is a necessary first step in most further algorithms. Computing Green’s relations
is equivalent to determining strongly connected components in the left and right Cayley graphs of a
semigroup, for which there are several well-known algorithms, such as Tarjan’s or Gabow’s. Hence the
problem of determining the Green’s relations of a semigroup represented by a generating set can be reduced
to the problem of finding the Cayley graphs. Thus the performance of algorithms for finding Cayley graphs
has a critical influence on the majority of further algorithms for finite semigroups.
The Froidure-Pin Algorithm involves determining all of the elements of the semigroup hAi and storing
them in the memory of the computer. In certain circumstances, it is possible to fully determine the
structure of hAi without enumerating and storing all of its elements. One such example is the SchreierSims Algorithm for permutation groups; see [6,15,16]. In [2], based on [8–10], the Schreier-Sims Algorithm
is utilised to compute any subsemigroup hAi of a regular semigroup U . Of course, this method is most
efficient when trying to compute a semigroup containing relatively large, in some sense, subgroups. In
other cases, it is not possible to avoid enumerating and storing all of the elements of hAi. For example, if
a semigroup S is J -trivial, then the algorithms from [2] enumerate all of the elements of S by multiplying
1

all the elements by all the generators, with the additional overheads that the approach in [2] entails. For
semigroups of this type, the algorithms in [2] perform significantly worse than the Froidure-Pin Algorithm.
In this paper, we present two algorithms based on the Froidure-Pin Algorithm from [4]. The first
algorithm (Algorithm 4.3 (Closure)) can be used to extend the output of the Froidure-Pin Algorithm for
a given semigroup hAi, to compute a supersemigroup hA, Bi without recomputing hAi. This algorithm
might be useful for several purposes, such as for example: in combination with Tietze transformations to
change generators or relations in a presentation for hAi; finding small or irredundant generating sets for
hAi; computing the maximal subsemigroups of certain semigroups [1].
The second algorithm (Algorithm 5.6 (ConcurrentFroidurePin)) is a lock-free concurrent version of the
Froidure-Pin Algorithm. Since computer processors are no longer getting faster, only more numerous, the
latter provides a means for fully utilising contemporary machines for computing finite semigroups.
If S is a semigroup generated by a set A, then the time and space complexity of the Froduire-Pin
Algorithm is O(|S||A|). Hence for example, in the case of transformation semigroups of degree n, the
worst case complexity is at least O(nn ). The algorithms presented here do not improve on the underlying
complexity of the Froduire-Pin Algorithm but offer practical improvements on the runtime.
Both algorithms are implemented in the C++ library libsemigroups [11], which can be used in both
GAP [12] and Python [3].
The paper is organised as follows. Some relevant background material relating to semigroups is given
in Section 2. In Section 3 we describe the Froidure-Pin Algorithm and prove that it is valid. While there
is much overlap between Section 3 and [4], this section is necessary to prove the validity of Algorithms 4.3
and 5.6, and because some details are omitted from [4]. Additionally, our approach is somewhat different to
that of Froidure and Pin’s in [4]. The first of our algorithms, for computing hA, Bi given hAi, is described
in Section 4, and the lock-free concurrent version of the Froidure-Pin algorithm is described in Section 5.
Sections 4 and 5 both contain empirical information about the performance of the implementation our
algorithms in libsemigroups [11], and our implementation of Froidure and Pin’s original algorithm in
libsemigroups. The performance of libsemigroups is roughly the same as that of Pin’s implementation
in Semigroupe 2.01 [14].

2

Preliminaries

In this section, we recall some standard notions from the theory of semigroups; for further details see [7].
If f : X −→ Y is a function, then dom(f ) = X and im(f ) = f (X) = {f (x) : x ∈ X}. If S is a
semigroup and T is a subset of S, then T is a subsemigroup if ab ∈ T for all a, b ∈ T . A semigroup S is a
monoid if it has an identity element, i.e. an element 1S ∈ S such that 1S s = s1S = s for all s ∈ S.
If A is a subset of a semigroup S, then we denote by hAi the smallest subsemigroup of S containing
A, and refer to A as the generators or generating set of hAi. If A is a generating set for a semigroup S,
then the right Cayley graph of a semigroup S with respect to A is the digraph with vertex set S and an
edge from s to sa for all s ∈ S and a ∈ A. The left Cayley graph of S is defined analogously.
A congruence ρ on a semigroup S is an equivalence relation on S which is invariant under the multiplication of S. More precisely, if (x, y) ∈ ρ, then (xs, ys), (sx, sy) ∈ ρ for all s ∈ S. A homomorphism from a
semigroup S to a semigroup T is just a function f : S −→ T such that f (xy) = f (x) f (y) for all x, y ∈ S.
If ρ is a congruence on a semigroup S, then the quotient S/ρ of S by ρ is the semigroup consisting of the
equivalence classes {s/ρ : s ∈ S} of ρ with the operation
x/ρ y/ρ = (xy)/ρ
for all x, y ∈ S. If f : S −→ T is a homomorphism of semigroups, then the kernel of f is
ker(f ) = {(x, y) ∈ S × S : f (x) = f (y)},
and this is a congruence. There is a natural isomorphism between S/ ker(f ) and im(f ) which is a subsemigroup of T .
An alphabet is just a finite set A whose elements we refer to as letters. A word is just a finite sequence
w = (a1 , . . . , an ) of letters a1 , . . . , an in an alphabet A. For convenience, we will write a1 · · · an instead of
(a1 , . . . , an ). The length of a word w = a1 · · · an ∈ A∗ is n and is denoted |w|. A non-empty subword of a
word a1 · · · an is a word of the form ai ai+1 · · · aj where 1 ≤ i ≤ j ≤ n.
The free semigroup over the alphabet A is the set of all words over A with operation the concatenation
of words; we denote the free semigroup on A by A+ . The free semigroup A+ has the property that every
2

function f : A −→ S, where S is a semigroup, can be uniquely extended to a homomorphism ν : A+ −→ S
defined by ν(a1 · · · an ) = f (a1 ) f (a2 ) · · · f (an ) for all a1 · · · an ∈ A+ . We denote the monoid obtained from
A+ by adjoining the empty word by A∗ ; which is called the free monoid.
Suppose that < is a well-ordering of A. Then < induces a well-ordering on A∗ , also denoted by <,
where u < v if |u| < |v| or there exist p, u0 , v 0 ∈ A∗ and a, b ∈ A, a < b, such that u = pau0 and v = pbv 0 .
We refer to < as the short-lex order on A∗ . Let S be a semigroup and let A ⊆ S. Then there exists a
unique homomorphism ν : A+ −→ S that extends the inclusion function from A into S. The word u ∈ A+
such that
u = min{v ∈ A+ : ν(u) = ν(v)},
with respect to the short-lex order on A+ , is referred to as a reduced word for S. For every word w ∈ A+ ,
there is a unique reduced word for S, which we denote by w.
We require the following results relating to words and the short-lex order <.
Proposition 2.1 (cf. Proposition 2.1 in [4]). Let A be any alphabet, let u, v, x, y ∈ A∗ , and let a, b ∈ A.
Then the following hold:
(a) if u < v, then au < av and ua < va;
(b) if ua ≤ vb, then u ≤ v;
(c) if u ≤ v, then xuy ≤ xvy.
Proposition 2.2 (cf. Proposition 2.1 in [17]). If S is a semigroup, A ⊆ S, and w ∈ A+ is reduced for S,
then every non-empty subword of w is reduced.
Throughout this paper, we refer to the semigroup U as the universe, and we let S be a subsemigroup
of U represented by a finite set A of generators. The algorithms described herein require that we can:
• compute the product of two elements in U ; and
• test the equality of elements in U .
In each of the main algorithms presented in this paper, rather than obtaining the actual elements
of the subsemigroup S we obtain reduced words representing the elements of S. This is solely for the
simplicity of the exposition in this paper, and is equivalent to using the actual elements of S by the
following proposition.
Proposition 2.3 (cf. Proposition 2.3 in [4]). If S is a semigroup, A ⊆ S, ν : A+ −→ S is the unique
homomorphism extending the inclusion of A into S, then the set R = {w : w ∈ A∗ } with the operation
defined by u · v = uv is a semigroup isomorphic to S.

3

The Froidure-Pin Algorithm

In this section we describe a version of the Froidure-Pin Algorithm from [4] and prove that it is valid.
Throughout this section, let U be any semigroup, let S be a subsemigroup of U generated by A ⊆ U
where 1U ∈ A, and let ν : A+ −→ S be the unique homomorphism extending the inclusion function of
A into S. Since ν(a) = a for all a ∈ A, we can compute ν(s) for any s ∈ A+ by computing products of
elements in S.
We require functions f, l : A+ −→ A and p, s : A+ −→ A∗ defined as follows:
• if w ∈ A+ and w = au for some a ∈ A and u ∈ A∗ , then f (w) = a and s(w) = u, i.e. f (w) is the
first letter of w and s(w) is the suffix of w with length |w| − 1;
• if w ∈ A+ and w = vb for some b ∈ A and v ∈ A∗ , then l(w) = b and p(w) = v, i.e. l(w) is the last
letter of w and p(w) is the prefix of w with length |w| − 1.
Note that if w ∈ A, then both p(w) and s(w) equal the empty word.
Next, we give formal definition of the input and output of the version of the Froidure-Pin Algorithm
described in this section. A less formal discussion of the definition can be found below.
Definition 3.1. The input of our version of the Froidure-Pin Algorithm is a snapshot of S which is a
tuple (A, Y, K, B, φ) where:
3

(a) A = {a1 , . . . , ar } is a finite collection of generators for S where a1 < · · · < ar for some r ∈ N;
(b) A ⊆ Y = {y1 , . . . , yN } is a collection of reduced words for S, y1 < y2 < · · · < yN , and if x ∈ A+ is
reduced, then either x ∈ Y or x > yN , for some N ∈ N;
(c) K ∈ N and 1 ≤ K ≤ |Y | + 1;
(d) either B = ∅ or B = {a1 , . . . , as } for some 1 ≤ s ≤ r; and
(e) if K ≤ |S|, then φ is a function from



A × {y1 , . . . , yL } ∪ {y1 , . . . , yK−1 } × A ∪ {yK } × B
to Y such that ν(φ(u, v)) = ν(uv) for all u, v ∈ dom(φ) and either L = K − 1 or L < K − 1 and L is
the largest value such that |yL | < |yK−1 |.
Note that by part (e) of Definition 3.1, φ(u, v) ≤ uv for all u, v ∈ dom(φ) since φ(u, v) ∈ Y is reduced
and both uv and φ(u, v) represent the same element of S. If in parts (c) and (e) of Definition 3.1, L = K −1
and B = A, respectively, then the snapshot (A, Y, K, B, φ) could be written as the snapshot (A, Y, K +
1, ∅, φ) instead. We allow both formulations so that Algorithm 3.1 (Update) is more straightforward.
Roughly speaking, in Definition 3.1, part (b) say that Y consists of all the reduced words for S which
are less than or equal to yN . The set Y consists of those elements of S that have been found so far in our
enumeration. The K in part (c) is the index of the next element in Y that will be multiplied on the right
by some of the generators A. More precisely, yK will be multiplied by the least element in A \ B where B
is given in part (d). The function φ in part (e) represents a subgraph of the right and left Cayley graphs
of S with respect to A. More specifically, if B 6= A, then K is the index of the first element in Y where not
all of the right multiples yK a where a ∈ A are yet known. Similarly, L is the index of the last element in
Y where all of the left multiples of yL are known. Condition (e) indicates that if any right multiples of a
reduced word w for S are known, then the left multiples of all reduced words of length at most |w| − 1 are
also known. The condition also allows the left multiples of all reduced words of length |w| to be known.
The output of our version of the Froidure-Pin Algorithm is another snapshot of the above type where:
the output value of K is at least the input value; the output value of Y contains the input value as a
subset; and the output function φ is an extension of the input function. In this way, we say that the
output snapshot extends the input data structure. In other words, if K ≤ |S| or Y 6= S, then the output
snapshot contains more edges in the right Cayley graph than the input snapshot, and may contain more
elements of S, and more edges in the left Cayley graph.
The parameters |Y | and K quantify the state of the Froidure-Pin Algorithm, in the sense that the
minimum values are |Y | = |A| and K = 1, and the snapshot is complete when K = |S| + 1 = |Y | + 1,
which means that Y = S and all of the edeges of the left and right Cayley graphs of S are known. We say
that a snapshot of S is incomplete if it is not complete. If desirable the Froidure-Pin Algorithm can be
halted before the output snapshot is complete (when K ≤ |S|), and subsequently continued and halted,
any number of times. Such an approach might be desirable, for example, when testing if u ∈ U belongs to
S, we need only run the Froidure-Pin Algorithm until u is found, and not until K = |S| + 1 unless u 6∈ S.
The minimal snapshot required by the Froidure-Pin Algorithm for S = hAi is:
(A, A, 1, ∅, ∅);

(3.2)

where the only known elements are the generators, and no left nor right multiples of any elements are
known.
If (A, Y, K, B, φ) is a snapshot of the semigroup S, then |Y | is referred to as its size, its elements are
the elements of Y , and x ∈ S belongs to the snapshot if the reduced word corresponding to x belongs to
Y , i.e. x = ν(w) for some w ∈ Y .
Algorithm 3.1 (Update) is an essential step in the Algorithm 3.2 (Froidure-Pin) and we will reuse
(Update) in Algorithm 4.3 (Closure). Roughly speaking, Update adds the first unknown right multiple to
an incomplete snapshot. In Update a multiplication is only performed if it is not possible to deduce the
value from existing products in the input snapshot. Deducing the value of a right multiple is a constant
time operation, whereas performing the multiplication almost always has higher complexity. For example,
matrix multiplication is at least quadratic in the number of rows. This is the part of the Froidure-Pin
Algorithm that is responsible for its relatively good performance.

4

Algorithm 3.1: Update: adds the first unknown right multiple to an incomplete snapshot
Input: An incomplete snapshot (A, Y, K, B, φ) for a semigroup S where B 6= A
Output: A snapshot extending (A, Y, K, B, φ) that contains yK a where a = min(A \ B)
1 if φ(s(yK ), a) < s(yK )a then
s(yK )a is not reduced, and so yK a is not reduced
2
φ(s(yK ), a) = yi for some yi ∈ Y
3
φ(yK , a) := φ(φ(f (yK ), p(yi )), l(yi ))
4 else if ν(yK a) = ν(yi ) for some i ≤ |Y | then
s(yK )a is reduced but yK a is not
5
φ(yK , a) := yi
6 else
yK a is reduced
7
y|Y |+1 := yK a and Y ← Y ∪ {y|Y |+1 }
8
φ(yK , a) := y|Y |+1
9

return (A, Y, K, B ∪ {a}, φ)

Recall that since ν(a) = a for all a ∈ A and ν is a homomorphism, the value of ν(w) ∈ S can be
determined for any w ∈ A+ by computing products in S. In practice, we perform the single multiplication
ν(yK ) ν(a) = ν(yK a).
Lemma 3.3. If (A, Y, K, B, φ) is a snapshot of a semigroup S, B 6= A, and a is the least generator in
A \ B, then Algorithm 3.1 (Update) returns a snapshot of S containing yK a.
Proof. There are three cases to consider:
(a) s(yK )a is not reduced
(b) ν(yK a) = ν(yi ) for some i ≤ N
(c) neither (a) nor (b) holds.
If (a) or (b) holds, then the only component of the snapshot that is modified is φ, and so we must verify
that φ is well-defined, and satisfies Definition 3.1(e). In the case when (c) holds, we also need to show
that Definition 3.1(b) holds.
(a). In this case, φ(s(yK ), a) ∈ Y is defined because s(yK ) ∈ Y and s(yK ) < yK . Hence there exists
i ≤ N such that φ(s(yK ), a) = yi . Since p(yi )l(yi ) = yi < s(yK )a, by Proposition 2.1(b), p(yi ) ≤ s(yK )
and s(yK ) < yK since |s(yK )| < |yK |. Hence φ(f (yK ), p(yi )) is defined and
φ(f (yK ), p(yi )) ≤ f (yK )p(yi ) < f (yK )s(yK ) = yK .
By the definition of φ and since ν is a homomorphism,
ν(yK a)

= ν(f (yK )s(yK )a) = ν(f (yK ))ν(s(yK )a) = ν(f (yK ))ν(φ(s(yK ), a))
=

ν(f (yK ))ν(yi ) = ν(f (yK )yi ) = ν(f (yK )p(yi ))ν(l(yi ))

=

ν(φ(f (yK ), p(yi )))ν(l(yi )) = ν(φ(f (yK ), p(yi ))l(yi ))

=

ν(φ(φ(f (yK ), p(yi )), l(yi ))).

Hence if φ(yK , a) := φ(φ(f (yK ), p(yi )), l(yi )), then φ continues to satisfy Definition 3.1(e).
(b). By the assumption of this case, ν(φ(yK , a)) = ν(yi ) = ν(yK a), and Definition 3.1(e) continues to
hold.
(c). In this case, yK a is reduced, and yK a ∈
/ Y . Hence yK a > max Y by Definition 3.1(b), and so
Y ∪ {y|Y |+1 } where y|Y |+1 = yK a satisfies the first part of Definition 3.1(b). If w ∈ A+ is reduced and
w < yK a = y|Y |+1 , then w = p(w)l(w) < yK a and so either p(w) < yK or l(w) < a by Proposition 2.1. In
both cases, (p(w), l(w)) ∈ dom(φ), and so w = φ(p(w), l(w)) ∈ Y and so Definition 3.1(b) holds.
By the assumption of this case ν(yK a) 6= ν(yi ) for any yi ∈ Y , and so, in particular, yK a 6∈ Y . On the
other hand, yK a ≤ yK a and yK a < yK a implies yK a ∈ Y from the previous paragraph. Hence yK a = yK a
is reduced. Finally, ν(φ(yK , a)) = ν(y|Y |+1 ) = ν(yK a) by definition and so Definition 3.1(e) holds.
Next we state the Froidure-Pin Algorithm, a proof that the algorithm is valid follows from Lemmas 3.3
and 3.4.

5

Algorithm 3.2: FroidurePin: enumerate at least min{M, |S|} elements of a semigroup S.
Input: A snapshot (A, Y, K, ∅, φ) for a semigroup S and a limit M ∈ N
Output: A snapshot of S which extends (A, Y, K, ∅, φ) and with size at least min{M, |S|}
1 while K ≤ |Y | and |Y | < M do
2
c := |yK |
3
while K ≤ |Y | and |yK | = c and |Y | < M do
4
B := ∅
5
while B \ A 6= ∅ do
loop over the generators A in (short-lex) order
6
(A, Y, K, B, φ) ← Update(A, Y, K, B, φ)
7
8
9
10
11
12

13

K ←K +1
if K > |Y | or |yK | > c then
L = max{i ∈ N : |yi | < c}
for i ∈ {L + 1, . . . , K − 1} do
for a ∈ A do
φ(a, yi ) := φ(φ(a, p(yi )), l(yi ))

indices of words of length one less than yK
extend φ so that A × {yi } ⊆ dom(φ)

return (A, Y, K, ∅, φ)

Note that both the input, and output, of Algorithm 3.2 (FroidurePin) has fourth component equal to
∅, and as such it would appear to be unnecessary. However, it is used in the definition of a snapshot so
that we can succinctly describe the output of Closure. FroidurePin could be modified to return a snapshot
where the fourth component was not empty, but for the sake of relative simplicity we opted not to allow
this.
Lemma 3.4. If (A, Y, K, ∅, φ) is a snapshot of a semigroup S and M ∈ N, then Algorithm 3.2 (FroidurePin) returns a snapshot for S with at least min{M, |S|} elements.
Proof. We may suppose that K ≤ |Y | and |Y | < M , since otherwise FroidurePin does nothing.
By Lemma 3.3, after applying Update to the input snapshot and every a ∈ A, in line 6, (A, Y, K, A, φ)
is a snapshot of S containing yK A. At this point, if K ≤ |Y | and |yK+1 | = |yK |, then we continue the
while-loop starting in line 3. When we arrive in line 8 one of the following holds: K > |Y |, |Y | ≥ M , or
|yK | > c = |yK−1 |.
If the condition in line 8 is not satisfied, then the condition in line 3 is false because |Y | ≥ M . Hence the
condition in line 1 is also false, and so (A, Y, K, A, φ) is returned in this case. Since Algorithmn 3.1 (Update)
returns a snapshot, (A, Y, K, A, φ) could only fail to be a snapshot because the value of K was increased.
In other words, the tuple (A, Y, K, A, φ) satisfies Definition 3.1 (a) to (d) and ν(φ(u, v)) = ν(uv) for all
(u, v) ∈ dom(φ). Since the condition in line 8 is not satisfied, |yK | = |yK−1 | = c, and so (A, Y, K, A, φ)
continues to satisfy Definition 3.1(e), which is hence a snapshot of S, as required.
If the condition in line 8 is satisfied, then either K > |Y |; or K ≤ |Y | and |yK | > |yK−1 | = c. In either
case, the tuple (A, Y, K, B, φ) satisfies Definition 3.1(a) to (d), but may fail to satisfy part (e), since φ may
not be defined on A × {yL+1 , . . . , yK−1 }, where L ∈ N is the maximum value such that |yL | < |yK−1 | (as
defined in line 9). The only component of (A, Y, K, B, φ) that is modified within the if-clause is φ. Hence
by the end of the if-clause (A, Y, K, B, φ) is a snapshot for S, provided that φ(a, yi ) is well-defined for all
i ∈ {L + 1, . . . , K − 1} and ν(φ(a, yi )) = ν(ayi ) for all a ∈ A.
Let i ∈ {L + 1, . . . , K − 1}. Since |p(yi )| = |yi | − 1 and |yi | = |yK−1 |, φ(a, p(yi )) is defined and
|φ(a, p(yi ))| ≤ |ap(yi )| = |yK−1 |, because φ(a, p(yi )) ≤ ap(yi ). Since yK−1 is the largest reduced word of
length |yK−1 |, there exists j < K such that φ(a, p(yi )) = yj . By definition, (yj , x) ∈ dom(φ) for all x ∈ A.
In particular, φ(yj , l(yi )) = φ(φ(a, p(yi )), l(yi )) is defined, and so the assignment in line 12 is valid.
Let a ∈ A and i ∈ {L + 1, . . . , K − 1} be arbitrary. Then
ν(φ(a, yi ))

= ν(φ(φ(a, p(yi )), l(yi ))) = ν(φ(a, p(yi ))l(yi )) = ν(φ(a, p(yi ))) ν(l(yi ))
=

ν(ap(yi )) ν(l(yi )) = ν(ap(yi )l(yi ))

=

ν(ayi ),

as required.
6

Finally, the algorithm halts if |K| > |Y | in which case the snapshot contains |S| elements, or if |Y | ≥ M .
In either case, |Y | ≥ min{M, |S|}, as required.
Corollary 3.5. If (A, Y, K, ∅, φ) is a snapshot of a semigroup S and M ∈ N is such that M ≥ |S|, then
Algorithm 3.2 (FroidurePin) returns (A, R, |S|+1, ∅, φ) where R is the set of all reduced words for elements
of S and dom(φ) = (A × R) ∪ (R × A).
Proof. Suppose that the snapshot returned by FroidurePin is (A, Y, |S| + 1, ∅, φ).
Under the assumptions of the statement, the last iteration of while-loop starting in line 3 terminates
when K = |Y | + 1. Hence the condition of the if-clause in line 8 is satisfied, and so dom(φ) = (A × Y ) ∪
(Y × A).
Assume that there exists a reduced word w ∈ A+ such that w 6∈ Y . Then we may assume without loss
of generality that w is the minimum such reduced word. Hence p(w) is a reduced word and p(w) < w and
so p(w) ∈ Y . But then φ(p(w), l(w)) is defined, and so w = φ(p(w), l(w)) ∈ Y , a contradiction. Hence
Y = R.

4

The closure of a semigroup and some elements

In this section we give the first of the two new algorithms in this paper. Given a snapshot of a semigroup
S = hAi ≤ U and some additional generators X ⊆ U , this algorithm returns a snapshot for T = hA, Xi.
If ν : (A ∪ X)+ −→ T is the unique homomorphism extending the inclusion map from A ∪ X into T , then
ν restricted to A+ is the unique homomorphism extending the inclusion map from A into S. Hence we
only require the notation ν : (A ∪ X)+ −→ T .
The purpose of Algorithm 4.3 (Closure) is to avoid multiplying elements in the existing snapshot for S,
by the generators A, in the creation of the snapshot for T wherever such products are already known. The
principal complication is that the introduction of new generators can change the reduced word representing
a given element s of S. The new generating set A ∪ X may allow s to be written as a shorter word than
was previously possible with A. Suppose that {y1 , . . . , yKS } is the set of of those elements in the original
snapshot for S whose right multiples by the old generating set were known. Closure terminates when the
right multiplies by all the generators, old and new, of every element in {y1 , . . . , yKS } are known. In short
Closure is a version of FroidurePin where each of KS |A| products can be found in constant time. This
works particularly well when the addition of new generators does not increase the size of the semigroups
substantially, or when the complexity of multiplication is very high.
We prove that Closure is valid in Lemma 4.1.
Lemma 4.1. If (A, Y, KS , ∅, φS ) is a snapshot of a semigroup S ≤ U and X ⊆ U , then Algorithm 4.3
(Closure) returns a snapshot of T = hX, Ai that contains {y1 , . . . , yKS }X, and hence also contains Y .
Proof. At the start of Closure, (A ∪ X, Z, KT , B, φT ) is initialised as (A ∪ X, A ∪ X, 1, ∅, ∅), which is the
minimal snapshot of T by (3.2).
Additionally, λ : A −→ Z satisfies the following two conditions:
(a) dom(λ) = {y ∈ Y : ∃z ∈ Z, ν(y) = ν(z)}; and
(b) ν(λ(y)) = ν(y) for all y ∈ dom(λ).
If Y = dom(λ), then the minimal snapshot of T is returned, and there nothing to prove. So, suppose
that Y 6= dom(λ). We proved in Lemma 3.3, that Algorithm 3.1 (Update) returns a snapshot of T ,
given a snapshot of T . The data structure (A ∪ X, Z, KT , B, φT ) is otherwise only modified within the
while-loop starting on line 6, in the case that there exists yi ∈ Y such that ν(zKT ) = ν(yi ) and i < KS .
Hence it suffices to verify that after performing the steps in the if-clause starting in line 8 the tuple
(A ∪ X, Z, KT , B, φT ) is still a snapshot of T . In order to do this, we use the properties of λ given above.
Hence we must also check that λ continues to satisfy conditions (a) and (b) whenever it is modified (i.e.
in lines 13 and 20).
Suppose that λ satisfies conditions (a) and (b) above, and that there exists yi ∈ Y such that ν(zKT ) =
ν(yi ) and i < KS and that a ∈ A. Since i < KS , φS (yi , a) is defined for all a ∈ A.
If φS (yi , a) ∈ dom(λ), then in line 11 we define φT (zKT , a) = λ(φS (yi , a)). In this case, (A ∪
X, Z, KT , B, φT ) satisfies Definition 3.1(a) to (d) trivially and
ν(φT (zKT , a)) = ν(λ(φS (yi , a))) = ν(φS (yi , a)) = ν(yi a) = ν(zKT a).
7

Algorithm 4.3: Closure: add additional generators to a snapshot for a semigroup
Input: A snapshot (A, Y, KS , ∅, φS ) for a semigroup S ≤ U , and a collection of elements X ⊆ U \ Y
Output: A snapshot (A ∪ X, Z, KT , ∅, φT ) for T = hS, Xi that contains {y1 , . . . , yKS }X.
1 Define A = {z1 = y1 , . . . , zm = ym } and X = {zm+1 , . . . , zm+n }, z1 < z2 < · · · < zm+n
2 Z := A ∪ X, KT := 1, φT = ∅
initialise the snapshot for T
3 Define λ : A −→ Z to be the identity function on A
λ maps a reduced word for S to a
reduced word for T representing the same element, at this point A is the set
{y ∈ Y : ∃z ∈ Z, ν(y) = ν(z)}
4 while dom(λ) 6= Y do
there are reduced words in Y not yet in the snapshot for T
5
c := |zKT |
6
while dom(λ) 6= Y and |zKT | = c do
7
B := ∅
8
if ∃yi ∈ Y , ν(zKT ) = ν(yi ) and i < KS then
9
for a ∈ A do
loop over the old generators in (short-lex) order
10
if φS (yi , a) ∈ dom(λ) then
11
φT (zKT , a) := λ(φS (yi , a))
12
else
13
φT (zKT , a) := zKT a and λ(φS (yi , a)) := zKT a
14
z|Z|+1 := zK a and Z ← Z ∪ {zKT a}
15
16
17
18
19
20

B←A
while (A ∪ X) \ B 6= ∅ do
a := min{(A ∪ X) \ B}
(A ∪ X, Z, KT , B, φT ) ← Update(A ∪ X, Z, KT , B, φT )
if φT (zKT , a) = zKT a and ν(zKT a) = ν(yi ) for some yi ∈ Y then
λ(yi ) := zKT a

21
22
23
24
25
26
27

KT ← KT + 1
if KT > |Z| or |zKT | > c then
L = max{i ∈ N : |zi | < c}
for i ∈ {L + 1, . . . , KT − 1} do
for a ∈ A ∪ X do
φT (a, zi ) := φT (φT (a, p(zi )), l(zi ))

8

and so Definition 3.1(e) holds.
If φS (yi , a) 6∈ dom(λ), then we define φT (zKT , a) = zKT a. Since ν(φT (zKT , a)) = ν(zKT a) by definition,
it suffices to show that zKT a is a reduced word for T . Suppose, seeking a contradiction, that u ∈ (A ∪ X)+
is reduced, ν(u) = ν(yi a), and u < zKT a. Then either p(u) < zKT or p(u) = zKT and l(u) < a by
Propostion 2.1(b). In either case, φT (p(u), l(u)) = u is defined and so u ∈ Z. Thus ν(φS (yi , a)) =
ν(yi a) = ν(u) and so φS (yi , a) ∈ dom(λ) by (a), which contradicts the assumption of this case. Hence
zKT a is reduced. We must verify conditions (a) and (b) on λ after defining λ(φS (yi , a)) = zKT a ∈ Z in
line 13. Condition (a) holds, since we extended both Z and dom(λ) by a single value. Since
ν(λ(φS (yi , a))) = ν(zKT a) = ν(zKT )ν(a) = ν(yi )ν(a) = ν(yi a) = ν(φS (yi , a))
condition (b) also holds.
The only other part of the algorithm where λ is modified is line 20. Suppose that a = min((A ∪ X) \ B)
as defined in line 17. If φT (zKT , a) = zK a and ν(zKT ) = ν(yi ) for some yi ∈ Y , then zK a ∈ Z is reduced.
In this case, we define λ(yi ) = zKT a. Conditions (a) and (b) hold by the above argument.
We have shown that within the while-loop starting on line 6, the tuple (A ∪ X, Z, KT , B, φT ) satisfies
Definition 3.1(a) to (d). Additionally, we have shown that conditions (a) and (b) hold for λ.
The remainder of the proof follows by the argument given in the proof of Lemma 3.4.

4.1

Experimental results

In this section we compare the performance of Algorithm 3.2 (FroidurePin) and Algorithm 4.3 (Closure).
Further details about the computations performed, including code that can be used to reproduce the data,
in this section can be found in [13].
We note that in the implementation of Closure in libsemigroups [11], the snapshot of S = hAi is
modified in-place to produce the data structure for T = hA, Xi, and that none of the elements of S need
to be copied or moved in memory during Closure.
Figure 1, 2, 3, and 4 we plot a comparison of FroidurePin and Closure for 300 examples of randomly
generated semigroups. For a particular choice of A and X, three computations were run:
(1) a snapshot for hAi was enumerated using FroidurePin until it contained |hAi| elements; we denote the
time taken for this step by t1 .
(2) Closure was performed on the snapshot obtained from (1) and the generators X. We denote the size
of the snapshot obtained in this way by M and the time taken for this step by t2 .
(3) A snapshot for hA, Xi was enumerated using FroidurePin until it contained M (from (2)) elements.
We denote the time taken for this step by t3 .
A point on the x-axis of any graph in this section correspond to a single choice of A and X. The points
on the x-axes are sorted in increasing order according to the M/hAi. In other words, M/hAi indicates the
proportion of new elements generated in Closure. The y-axis corresponds to time divided by t3 from (3).
The triangles correspond to the mean value of t2 /t3 taken over 3 separate runs, and the crosses similarly
correspond to (t1 + t2 )/t3 .
The values of A and X in Figure 1 were chosen as follows:
• the collection A was chosen to have size between 2 and 30 elements (uniformly at random) and to
consist of 6 × 6 Boolean matrices, which were chosen uniformly at random from the space of all such
Boolean matrices.
• the collection X was taken to consist of a single 6 × 6 Boolean matrices, again chosen uniformly at
random.
The values of A and X in Figure 2 were chosen in a similar fashion from the space of all transformations
of degree 7, where |A| ∈ {2, . . . , 8} and X was chosen so that |X| = 1. In Figures 3 and 4, A and X were
chosen in the same way as collections of Boolean matrices, and transformations, with |A|, |X| ∈ {2, . . . , 30},
and |A|, |X| ∈ {2, . . . , 8}, respectively. The semigroups in Figures 1, 2, 3, and 4 range in size from 1767 to
681973, with time to run FroidurePin and Closure roughly in the range 10 to 1500 milliseconds, particular
values chosen for A and X can be found in the table below. We rejected those choices of A and X where

9

Ratio of runtime to runtime of FroidurePin( A X , M).

Closure( A , X)
Closure( A , X) + FroduirePin( A )

1.4
1.2
1.0
0.8

M/ A

0.6

2

0.4
0.2
0.0
0

50

100

150

200

250

300

Figure 1: A and X consist of 6 × 6 Boolean matrices, |A| ∈ {2, . . . , 30}, |X| = 1, M is the size of the
snapshot for hA, Xi returned by Algorithm 4.3 (Closure).
the time t1 to enumerate hAi using FroidurePin was less than 10 milliseconds, to reduce the influence of
random noise in the resulting data.
The range of values for |A|, the dimensions of these matrices, and degrees of these transformations were
chosen so that the resulting semigroups were not too large or small, and it was possible to run FroidurePin
on these semigroups in a reasonable amount of time.
It is not surprising to observe that when M/hAi is large that there is little benefit, or even a penalty, for
running Closure. This due to the fact that the run time t1 of FroidurePin on hAi is small in comparison to t2
and t3 . In this case, in Closure applied to hAi and X, only a relatively small proportion of multiplications
can be deduced, and so Closure is essentially doing the same computation as FroidurePin, but with an
additional overhead. It does appear from these examples, that Closure is beneficial when M/hAi ≤ 2.

5

A lock-free concurrent version of the Froidure-Pin Algorithm

In this section we describe a version of the Froidure-Pin Algorithm that can be applied concurrently
in multiple distinct processes. Roughly speaking, the idea is to split a snapshot of a semigroup S into
fragments where an algorithm similar to Algorithm 3.2 (FroidurePin) can be applied to each fragment
independently. Similar to the Froidure-Pin Algorithm the value of a right multiple of an element with a
generator is deduced whenever possible. If such a right multiple cannot be deduced, then it is stored in a
queue until all fragments are synchronised. The original Froidure-Pin Algorithm already offers a natural
point for this synchronisation to occur, when the right multiples of all words of a given length have been
determined. In the concurrent algorithm, the fragments are synchronised at exactly this point. In this
way, the concurrent algorithm has two phases: the first when right multiples are determined, and the
second when the fragments are synchronised. Some of the deductions of products that are made by the
original Froidure-Pin Algorithm cannot be made in our concurrent version. This happens if the information
required to make a deduction is, or will be, contained in a different fragment. In order to avoid locking, a
fragment does not have access to any information in other fragments during the first phase. In the second
phase, each fragment F can only access the words queued by all fragments for F . While this means that
the concurrent algorithm potentially performs more actual multiplications of elements than the original, in
Section 5.1 we will see that these numbers of multiplications are almost the same. Of course, we could have
10

Ratio of runtime to runtime of FroidurePin( A X , M).

1.6
1.4
1.2
1.0
0.8
0.6
0.4

M/ A

0.2

2

Closure( A , X)
Closure( A , X) + FroduirePin( A )

0.0
0

50

100

150

200

250

300

Ratio of runtime to runtime of FroidurePin( A X , M).

Figure 2: A and X consist of transformations of degree 7, |A| ∈ {2, . . . , 8}, |X| = 1, M is the size of the
snapshot for hA, Xi returned by Algorithm 4.3 (Closure).

Closure( A , X)
Closure( A , X) + FroduirePin( A )

1.4
1.2
1.0
0.8
0.6

M/ A

2

0

50

0.4
0.2
0.0
100

150

200

250

300

Figure 3: A and X consist of 6 × 6 Boolean matrices, |A|, |X| ∈ {2, . . . , 30}, M is the size of the snapshot
for hA, Xi returned by Algorithm 4.3 (Closure).

11

Ratio of runtime to runtime of FroidurePin( A X , M).

1.4
1.2
1.0
0.8
0.6
M/ A

0.4
0.2

2

Closure( A , X)
Closure( A , X) + FroduirePin( A )

0.0
0

50

100

150

200

250

300

Figure 4: A and X consist of transformations of degree 7, |A|, |X| ∈ {2, . . . , 8}, M is the size of the
snapshot for hA, Xi returned by Algorithm 4.3 (Closure).
allowed the fragments to communicate during the first phase but in our experiments this was significantly
slower. The evidence presented in Section 5.1 supports this, the time spent waiting for other fragments to
provide information outweighs the benefit of being able to deduce a relatively small additional number of
products.
Throughout this section, we again let U be any semigroup, let S be a subsemigroup of U generated by
A ⊆ U , and let ν : A+ −→ S be the unique homomorphism extending the inclusion map. We also define
f, l : A+ −→ A and p, s : A+ −→ A∗ to be the functions defined at the start of Section 3.
The following is the precise definition of a fragment required for our concurrent algorithm.
Definition 5.1. A fragment for S is a tuple (A, Y, K, φ) where:
(a) A = {a1 , . . . , ar } is a finite collection of generators for S where a1 < · · · < ar ;
(b) Y = {y1 , . . . , yN } is a collection of reduced words for S and y1 < y2 < · · · < yN ;
(c) 1 ≤ K ≤ |Y | + 1 and if K = 1, then Y = A, or if K > 1, then yK−1 = max{yi ∈ Y : |yi | = |yK−1 |};
(d) if R ⊆ A+ is the set of all reduced words for elements of S, then


φ : A × {y1 , . . . , yL } ∪ {y1 , . . . , yK−1 } × A −→ R
where ν(φ(u, v)) = ν(uv) for all u, v ∈ dom(φ) and either:
(i) L = K − 1; or
(ii) L < K − 1 and L is the largest value such that |yL | < |yK−1 |.
Note that in part (c) the condition that yK−1 = max{yi ∈ Y : |yi | = |yK−1 |} implies that either yK
does not exist or |yK | > |yK−1 |. We refer to the size, elements, extension, and so on of a fragment for a
semigroup S, in the same way as we did for the snapshots of S.
We suppose throughout this section that however φ in Definition 5.1 is actually implemented, it supports
concurrent reads of any particular value φ(x, y) when (x, y) ∈ dom(φ) and that it is possible to define φ(x, y)
for any (x, y) 6∈ dom(φ) concurrent with any read of φ(x0 , y 0 ) for (x0 , y 0 ) ∈ dom(φ). Of course, the difficulty
12

is that we do not necessarily know whether (x, y) belongs to dom(φ) or not. If one process is defining
φ(x, y) and another is trying to read φ(x, y), it is not possible to determine whether (x, y) belongs to
dom(φ) without locking, which we want to avoid. We avoid this in Algorithm 5.6 (ConcurrentFroidurePin)
because φ is defined for those (w, a) and (a, w) where a ∈ A and w is a reduced word whose length is
strictly less than the minimum length of a word some of whose right multiples are not known.
The implementation in libsemigroups [11] represents φ as a pair of C++ Standard Template Library
vectors, which support this behaviour provided that no reallocation occurs when we are defining φ(x, y) for
(x, y) 6∈ dom(φ). In ConcurrentFroidurePin, all of the reduced words w ∈ A+ of a given length are produced
before any value of φ(w, a) or φ(a, w) is defined, and so we can allocate enough memory to accommodate
these definitions and thereby guarantee that it is safe to read and write values of φ(x, y) concurrently.
If (A, A, 1, ∅, ∅) is a minimal snapshot for S, we refer to the collection of fragments
(A, {a ∈ A : b(a) = j}, 1, ∅) j ∈ {1, . . . , k}
as a minimal collection of fragments for S.
The next lemma describes when some fragments for S can be assembled into a snapshot of S.
Lemma 5.2. Suppose that (A, Y1 , K1 , φ1 ), . . . , (A, Yk , Kk , φk ) is a collection of fragments for S which is
either minimal or Yi = {yi,1 , . . . , yi,Ni } and the following hold:
(i) Yi ∩ Yj = ∅ for all i, j, i 6= j;
(ii) for all reduced w ∈ A+ either
w∈

k
[

Yi

or

w > max

i=1

k
[

Yi ;

i=1

(iii) if Kj > 1, then |yj,Kj −1 | = max{|y| : y ∈ Yj , |y| ≤ c} where c = max{|yi,Ki −1 | : 1 ≤ i ≤ k, Ki > 1}
(iv) dom(φi ) = (A × {yi,1 , . . . , yi,Ki −1 }) ∪ ({yi,1 , . . . , yi,Ki −1 } × A) for all i; and
Sk
(v) im(φi ) ⊆ j=1 Yj for all i.
Sk
If Y = i=1 Yi = {y1 , . . . , yN }, y1 < · · · < yN , K ∈ N is such that yK−1 = max{y ∈ Y : |y| = c}, and
Sk
φ = i=1 φi , then (A, Y, K, ∅, φ) is a snapshot of S.
Proof. If the collection of fragments is minimal, then clearly the union, as defined in the statement, is a
minimal snapshot for S.
Suppose that the collection of fragments is not minimal. It follows that there exists i ∈ {1, . . . , k} such
that Ki > 1, and so the value c in part (iii) is well-defined. It is clear that Definition 3.1(a) to (d) are
satisfied. It therefore suffices to show that part (e) of Definition 3.1 holds. Part (i) of the assumption of
this lemma implies that φ is well-defined. It suffices to verify that
dom(φ) = (A × {y1 , . . . , yK−1 }) ∪ ({y1 , . . . , yK−1 } × A),

im(φ) ⊆ Y,

and ν(φ(u, v)) = ν(uv)

for all u, v ∈ dom(φ). That im(φ) ⊆ Y follows from (v). If (u, v) ∈ dom(φ), then (u, v) ∈ dom(φi ) for
some i, and so ν(φ(u, v)) = ν(φi (u, v)) = ν(uv).
Let (a, yi ) ∈ A × {y1 , . . . , yK−1 }. Then yi ∈ Yj for some j and so yi = yj,t for some t. But |yj,t | =
|yi | ≤ |yj,Kj −1 | by the definition of K and part (iii) of the assumption of this lemma. Hence either
|yj,t | < |yj,Kj −1 | and so yj,t < yj,Kj −1 , or |yj,t | = |yj,Kj −1 | and, by Definition 5.1(c), yj,t < yj,Kj −1 . In
either case, t ≤ Kj − 1, and so (a, yi ) = (a, yj,t ) ∈ dom(φj ) ⊆ dom(φ). If (yi , a) ∈ {y1 , . . . , yK−1 } × A,
then (yi , a) ∈ dom(φ) by a similar argument.
If (a, yi ) ∈ dom(φ), then (a, yi ) ∈ dom(φj ) for some j. Hence yi ∈ {yj,1 , . . . , yj,Kj −1 }. It follows
that, since yK−1 = max{y ∈ Y : |y| = c}, yK−1 ≥ yj,Kj −1 ≥ yi , and so (a, yi ) ∈ A × {y1 , . . . , yK−1 }.
If (yi , a) ∈ dom(φ), then (yi , a) ∈ {yi,1 , . . . , yi,Ki −1 } × A by a similar argument. Therefore dom(φ) =
(A × {y1 , . . . , yK−1 }) ∪ ({y1 , . . . , yK−1 } × A), as required.
In Algorithm 5.4 (ApplyGenerators), and more generally in our concurrent version of the Froidure-Pin
Algorithm, we require a method for assigning reduced words w ∈ A+ that do not belong to any existing
fragment for S, to a particular fragment for S. If we want to distribute S into k fragments, then we let
13

b : R := {w ∈ A+ : w is reduced for S} −→ {1, . . . , k} be any function. Preferably so that our algorithms
are more efficient, b should have the property that |b−1 (i)| is approximately equal to |R|/k for all i. For
example, we might take a hash function for ν(w) modulo k, as the value of b(w). If the number of fragments
k = 1 or b(w) is constant for all reduced words w for S, then ConcurrentFroidurePin is just FroidurePin with
some extra overheads.
Algorithm 5.4: ApplyGenerators
Input: A collection of fragments (A, Y1 , K1 , φ1 ), . . . , (A, Yk , Kk , φk ) for a semigroup S satisfying
the hypothesis of Lemma 5.2 and j ∈ {1, . . . , k}.
Output: A set Qj = {(b(w), w) : |w| = c + 1} ⊆ {1, . . . , k} × A+ \ (Y1 ∪ · · · ∪ Yk ) where
c = max{|yi,Ki −1 | : 1 ≤ i ≤ k} and the tuple (A, Yj , Kj , φj ).
1 Qj := ∅
Qj is a container for new words
2 while Kj ≤ |Yj | and |yj,Kj | = c do
3
for a ∈ A do
loop over the generators in (short-lex) order
4
if φj (s(yj,Kj ), a) < s(yj,Kj )a then
s(yj,Kj )a is not reduced
5
y := φi (s(yj,Kj ), a) where s(yj,Kj ) ∈ Yi
6
w := φm (f (yj,Kj ), p(y)) ∈ Yn where p(y) ∈ Ym
7
if n = j or |w| < c then
8
φj (yj,Kj , a) := φn (w, l(y))
9
continue
10
11
12
13
14
15

if ν(yj,Kj a) = ν(y) for some y ∈ Y1 ∪ · · · ∪ Yk then
φj (yj,Kj , a) := y
else
Qj ← Qj ∪ {(b(yj,Kj a), yj,Kj a)}
Kj ← Kj + 1
return Qj and (A, Yj , Kj , φj )

Lemma 5.3. Algorithm 5.4 (ApplyGenerators) can be performed concurrently on each fragment (A, Yj , Kj , ∅, φj )
of its input.
Proof. Every value assigned to φj in ApplyGenerators equals a value for φ defined in Update. It is possible
that some assignments made in Update for φ cannot be made for φj in ApplyGenerators. In particular, in
Update if s(yj,Kj )a is not reduced, then φj (s(yj,Kj ), a) is always defined in Update but is only defined in
some cases in ApplyGenerators. Hence that φj is well-defined follows by the proof of Lemma 3.3.
The values φi (s(yj,Kj ), a), φm (f (yj,Kj ), p(y)), and φn (w, l(y)) are read in ApplyGenerators and may
belong to other fragments. But |s(yj,Kj )|, |p(y)| < c and φn (w, l(y)) is only used if n = j or |w| <
c. The only value which is written in ApplyGenerators is φj (yj,Kj , a), and |yj,Kj | = c. It follows that
ApplyGenerators only reads values of φd (u, a) or φd (a, u) when d 6= j and |u| < c, while the algorithm
only writes to values of φj (u, a) when |u| = c. Therefore there are no concurrent reads and writes in
ApplyGenerators.
Note that after applying ApplyGenerators, the tuple (A, Yj , Kj , φj ) is no longer a fragment because
Definition 5.1(d) may not be satisfied.
The next algorithm, Algorithm 5.5 (ProcessQueues), performs the synchronisation step alluded to at
the start of this section. We prove the validity of ProcessQueues in Lemma 5.4.
Lemma 5.4. Algorithm 5.5 (ProcessQueues) returns a fragment for S satisfying Definition 5.1(d)(ii) and
it can be performed concurrently on each j ∈ {1, . . . , k}.
Proof. If ProcessQueues is run concurrently in k processes, for distinct values of j, then each process only
writes to φj and only reads from Q1 ∪ · · · ∪ Qk . Hence ProcessQueues can be performed concurrently.
Parts (a) of Definition 5.1 holds trivially. For part (b), it suffices to note that wa added in line 6, is a
reduced word, since we loop over the elements in Q1 ∪ · · · ∪ Qk in short-lex order.
For part (c), we must show that 1 ≤ Kj ≤ |Yj | + 1 and that yj,Kj −1 is the maximum word in Yj of
length |yj,Kj −1 |. Since Kj is not modified by ProcessQueues the first condition holds. ApplyGenerators
14

Algorithm 5.5: ProcessQueues
Input: The output of Algorithm 5.4 (ApplyGenerators) for all m ∈ {1, . . . , k} and j ∈ {1, . . . , k}.
Output: A fragment for S extending (A, Yj , Kj , φj ), containing every reduced word wa such that
(j, wa) ∈ Q1 ∪ · · · ∪ Qk .
1 for (b(wa), wa) ∈ Q1 ∪ · · · ∪ Qk do
loop over Q1 ∪ · · · ∪ Qk in short-lex order on wa
2
if b(wa) = j then
3
if ν(wa) = ν(y) for some y ∈ Yj then
4
φj (w, a) = y
5
6
7
8

else
Yj ← Yj ∪ {wa}
φj (w, a) := wa
return (A, Yj , Kj , φj )

must have returned to obtain the input for ProcessQueues, which implies that yj,Kj −1 is the maximum
word in Yj of length |yj,Kj −1 | before ProcessQueues is called. ProcessQueues only adds words to Yj of
length c + 1 > |yj,Kj −1 | and so yj,Kj −1 is the maximum word in Yj , and part (c) holds.
For part (d), suppose that w ∈ Y1 ∪· · ·∪Yk and a ∈ A are such that φj (w, a) is defined in ApplyGenerators
or ProcessQueues. In either case, φj (w, a) ∈ Y and since we have shown that every element in Y is reduced,
φj (w, a) must be also.
The input of ApplyGenerators satisfies Lemma 5.3, in particular part (iv), which states that before
applying ApplyGenerators
dom(φj ) = (A × {y ∈ Yj : |y| < c}) ∪ ({y ∈ Yj : |y| < c} × A).
If a ∈ A and w ∈ Yn such that |w| = c and b(wa) = j, then either ApplyGenerators defines some φj (w, a) or
(j, wa) is placed in Qn . In the latter case, φj (w, a) is defined in ProcessQueues. Hence when ProcessQueues
returns


dom(φj ) = A × {yj,1 , . . . , yj,L } ∪ {yj,1 , . . . , yj,Kj −1 } × A
where L < Kj − 1 and L is the largest value such that |yL | < |yKj −1 |. That ν(φ(u, v)) = ν(uv) for all
u, v ∈ dom(φ) follows by the argument in the proof of Lemma 3.3.
We have all of the ingredients to state the concurrent version of Froidure-Pin, the validity of which is
proven in Lemma 5.5.
Lemma 5.5. If (A, Y, K, ∅, φ) is a snapshot for a semigroup S and M ∈ N, then Algorithm 5.6 (ConcurrentFroidurePin) returns a snapshot of S that extends (A, Y, K, ∅, φ) has at least min{M, |S|} elements.
Proof. By Lemma 5.3 and 5.4, when line 8 is reached, every tuple (A, Yj , Kj , φj ) is a fragment for S, and
the loops applying ApplyGenerators and ProcessQueues can be performed concurrently.
We will show that by the end of the for-loop started in line 8, (A, Y1 , K1 , φ1 ), . . . , (A, Yk , Kk , φk ) is
a collection of fragments satisfying the conditions of Lemma 5.2, and that the steps within the for-loop
can be executed concurrently for each fragment. That the values assigned to φj are valid follows by the
argument in the proof of Lemma 3.4. Suppose that j ∈ {1, . . . , k} is given. When the for-loop started in
line 8 is complete, (A, Yj , Kj , φj ) clearly satisfies Definition 5.1(a) to (c), since φj is the only component
which is modified inside the for-loop. Hence it suffices to verify Definition 5.1(d). That ν(φj (u, v)) = ν(uv)
for all u, v ∈ dom(φj ) follows again by the same argument as in Lemma 3.4.
By Lemma 5.4, before φj is modified in this loop it satisfies Definition 5.1(d)(ii), i.e.


dom(φj ) = A × {yj,1 , . . . , yj,L } ∪ {yj,1 , . . . , yj,Kj −1 } × A
where L < Kj − 1 is the largest value such that |yL | < |yKj −1 |. After the for-loop starting in line 10,


dom(φj ) = A × {yj,1 , . . . , yj,Kj −1 } ∪ {yj,1 , . . . , yj,Kj −1 } × A .
(5.6)
In other words, Definition 5.1(d)(i) holds, and so (A, Yj , Kj , φj ) is a fragment.

15

Algorithm 5.6: ConcurrentFroidurePin
Input: A collection of fragments (A, Y1 , K1 , φ1 ), . . . , (A, Yk , Kk , φk ) for a semigroup S satisfying
the hypothesis of Lemma 5.2 and M ∈ N.
Output: A collection of fragments (A, Y1 , K1 , φ1 ), . . . , (A, Yk , Kk , φk ) for a semigroup S satisfying
the hypothesis of Lemma 5.2 and with size at least min{M, |S|}.
1 c := max{|yi,Ki −1 | : 1 ≤ i ≤ k, Ki > 1} ∪ {1}
2 while ∃j Kj ≤ |Yj | and |Y1 ∪ . . . ∪ Yk | < M do
3
Q1 := ∅, . . . , Qk = ∅
4
for j ∈ {1, . . . , k} do
This can be done concurrently
5
Qj , (A, Yj , Kj , φj ) ← ApplyGenerators(A, Yj , Kj , φj )
for j ∈ {1, . . . , k} do
(A, Yj , Kj , φj ) ←ProcessQueues(Q, j)

6
7

This can be done concurrently

12

for j ∈ {1, . . . , k} do
This can be done concurrently
Lj = max{i ∈ N : |yj,i | < c, yj,i ∈ Yj }
for i ∈ {Lj + 1, . . . , Kj − 1} do
if {y ∈ Yj : |y| = c} = ∅, then Kj − 1 < Lj + 1
for a ∈ A do
φj (a, yj,i ) := φn (φm (a, p(yj,i )), l(yj,i )) where p(yj,i ) ∈ Ym and φm (a, p(yj,i )) ∈ Yn

13

c←c+1

8
9
10
11

14

c ← max{|yi,Ki −1 | : 1 ≤ i ≤ k, Ki > 1}

return (A, Y1 , K1 , φ1 ), . . . , (A, Yk , Kk , φk )

It is clear that the collection of fragments contains at least min{M, |S|} elements. Next, we show that
the for-loop started in line 8 can be executed concurrently. Since |p(yj,i )| < |yj,i | = c and so φm (a, p(yj,i ))
is defined before line 8. Furthermore, |φm (a, p(yj,i ))| ≤ |yj,i | = c and by, (5.6), φn (w, b) is defined for all
reduced w of length at most c and for all b ∈ A. In other words, φn (φm (a, p(yj,i )), l(yj,i )) is defined before
line 8.
It remains to show that the collection of fragments satisfies the conditions in Lemma 5.2. For
Lemma 5.2(i), a reduced word y belongs to Yj if and only if b(y) = j, and hence Yi ∩ Yj = ∅ if i 6= j. To
Sk
show that Lemma 5.2(ii) holds, it suffices to show that i=1 Yi = {w ∈ A+ : |w| ≤ |yN |, w is reduced}.
Suppose that w ∈ A+ is reduced and |w| ≤ |yN |. Then |p(w)| < |yN | and so p(w) ∈ {yj,1 , . . . , yj,Kj −1 } for
Sk
some j. Hence (p(w), l(w)) ∈ dom(φj ) and so w = φj (p(w), l(w)) ∈ i=1 Yi . Within ConcurrentFroidurePin
the values of Kj are only modified in the calls to ApplyGenerators. Every call to ApplyGenerators increases
Kj so that either |yj,Kj −1 | = c+1, or there are no words of length c+1 in the jth fragment. In other words,
Lemma 5.3(iii) holds. We showed in (5.6) that Lemma 5.2(iv) holds and Lemma 5.2(v) holds trivially.

5.1

Experimental results

In this section we compare the original version of Algorithm 3.2 (FroidurePin) as implemented in libsemigroups [11], and the concurrent version in Algorithm 5.6 (ConcurrentFroidurePin). The implementation
of ConcurrentFroidurePin in libsemigroups [11] uses thread based parallelism using C++11 Standard
Template Library thread objects.
We start by comparing the number of products of elements in S that are actually computed in FroidurePin and ConcurrentFroidurePin. In [4, Theorem 3.2], it is shown that the number of such products in
FroidurePin is |S| + |R| − |A| − 1 where R is the set of relations for S generated by FroidurePin. One of the
main advantages of the Froidure-Pin Algorithm, concurrent or not, is that it avoids multiplying elements
of S as far as possible by reusing information learned about S at an earlier stage of the algorithm. This
is particularly important when the complexity of multiplying elements in S is high. ConcurrentFroidurePin
also avoids multiplying elements of S, but is more limited in its reuse of previously obtained information.
The number of products of elements S depends on the number of fragments k used by ConcurrentFroidurePin and the function b : A∗ −→ {1, . . . , k}. The full transformation monoid Tn of degree n ∈ N consists of
all functions from {1, . . . , n} to {1, . . . , n} under composition of functions. It is generated by the following
transformations:

 
 

1 2 3 ··· n − 1 n
1 2 3 ··· n − 1 n
1 2 3 ··· n − 1 n
,
,
.
2 3 4 ···
n
1
2 1 3 ··· n − 1 n
1 2 3 ··· n − 1 1
16

n
|Tn | = nn
FroidurePin
ConcurrentFroidurePin
ConcurrentFroidurePin
ConcurrentFroidurePin
ConcurrentFroidurePin
ConcurrentFroidurePin
ConcurrentFroidurePin

(1 fragments)
(2 fragments)
(4 fragments)
(8 fragments)
(16 fragments)
(32 fragments)

3
27
40
45
45
47
46
46
46

4
256
340
405
415
406
405
402
404

5
3125
3877
4535
4586
4587
4589
4596
4563

6
46656
54592
66293
67835
67682
67433
67578
67755

7
823543
926136
1048758
1106562
1153668
1155484
1153832
1152818

8
16777216
18285899
20235231
22763829
23093948
23411798
23616000
23566915

Table 1: Comparison of the number of products of elements in Algorithms 3.2 (FroidurePin) and 5.6
(ConcurrentFroidurePin) applied to the full transformation monoid Tn .
We compare the number of products of elements of S in FroidurePin and ConcurrentFroidurePin for each of
k = 1, 2, 4, . . . , 32 fragments and for the full transformation monoid of degree n = 3, . . . , 8; see Figure 1.
The number of products in FroidurePin is a lower bound for the number in ConcurrentFroidurePin, and we
would not expect ConcurrentFroidurePin to achieve this bound. However, from the table in Figure 1 it can
be observed that the number of products in ConcurrentFroidurePin is of the same order of magnitude as
that in ConcurrentFroidurePin. In [4], it was noted that there are 678223072849 entries in the multiplication
table for T7 but only slightly less than a million products are required in FroidurePin; we note that only
slightly more than a million products are required in ConcurrentFroidurePin.
In Figures 5 and 6 we plot the performance of ConcurrentFroidurePin against the number of fragments
it uses for a variety of examples of semigroups S. As would be expected, if the semigroup S is relatively
small, then there is no advantage to using ConcurrentFroidurePin; see Figure 5. However, if the semigroup S
is relatively large, then we see an improvement in the runtime of ConcurrentFroidurePin against FroidurePin;
see Figure 6 and 7. Note that the monoid of reflexive 5 × 5 Boolean matrices has 1414 generators.
All of the computations in this section were run on a Intel Xeon CPU E5-2640 v4 2.40GHz, 20 physical
cores, and 128GB of DDR4 memory.

References
[1] C. Donoven, J. D. Mitchell, and W. Wilson, Computing maximal subsemigroups of a finite semigroup,
submitted https://arxiv.org/abs/1606.05583
[2] J. East, A. Egri-Nagy, J. D. Mitchell, and Y. Péresse, Computing finite semigroups, to appear in
Journal of Symbolic Computation, http://arxiv.org/abs/1510.01868
[3] Luke Elliot, Alex Levine, James D. Mitchell, and Nicolas M. Thiéry, libsemigroups python bindings,
https://github.com/james-d-mitchell/libsemigroups-python-bindings
[4] Véronique Froidure and Jean-Eric Pin, Algorithms for computing finite semigroups, In Foundations
of computational mathematics (Rio de Janeiro, 1997), pages 112–126. Springer, Berlin, 1997.
[5] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.8.7; 2017. http://www.
gap-system.org
[6] D. Holt with B. Eick and E. O’Brien, Handbook of computational group theory, CRC Press, Boca
Raton, Ann Arbor, London, Tokyo, 2004.
[7] John M. Howie, Fundamentals of semigroup theory, volume 12 of Londo, Mathematical Society Monographs. New Series, The Clarendon Press Oxford University Press, New York, 1995, Oxford Science
Publications.
[8] Janusz Konieczny, Green’s equivalences in finite semigroups of binary relations, Semigroup Forum,
48(2):235–252, 1994.
[9] Gerard Lallement and Robert McFadden, On the determination of Green’s relations in finite transformation semigroups, J. Symbolic Comput., 10(5):481–498, 1990.

17

[10] S. A. Linton, G. Pfeiffer, E. F. Robertson, and N. Ruškuc, Groups and actions in transformation
semigroups, Math. Z., 228(3):435–450, 1998.
[11] J. D. Mitchell et al,
libsemigroups - C++ library - version 0.3.1, May 2017,
james-d-mitchell.github.io/libsemigroups/

https://

[12] J. D. Mitchell et al, Semigroups - GAP package, Version 3.0.1, June 2017, http://gap-packages.
github.io/Semigroups/
[13] J. Jonušas and J. D. Mitchell, Benchmarking libsemigroups, https://james-d-mitchell.github.
io/2017-06-09-benchmarks/
[14] Jean-Eric Pin, Semigroupe 2.01: a software for computing finite semigroups, April 2009, https:
//www.irif.fr/~jep/Logiciels/Semigroupe2.0/semigroupe2.html
[15] Ákos Seress, Permutation group algorithms, volume 152 of Cambridge Tracts in Mathematics, Cambridge University Press, Cambridge, 2003.
[16] Charles C. Sims, Computational methods in the study of permutation groups, In Computational
Problems in Abstract Algebra (Proc. Conf., Oxford, 1967), pages 169–183. Pergamon, Oxford, 1970.
[17] Charles C. Sims, Computation with finitely presented groups, Encyclopedia of mathematics and its
applications, Cambridge University Press, Cambridge, England, New York, 1994.
[18] J. Rhodes and B. Steinberg, The q-theory of finite semigroups, Springer Monographs in Mathematics,
New York, 2009.

600

Full transformation monoid of degree 6
5x5 gossip monoid
5x5 upper triangular boolean matrices
5x5 unitriangular boolean matrices
6x6 unitriangular boolean matrices

500

Time in ms.

400
300
200
100
0

12 4

8

16
Number of fragments.

32

Figure 5: Run times for Algorithm 5.6 (ConcurrentFroidurePin) against number of fragments.

18

Full transformation monoid of degree 8
6x6 upper triangular boolean matrices
7x7 unitriangular boolean matrices
6x6 gossip monoid

35

Time in seconds.

30
25
20
15
10
5
0

12 4

8

16
Number of fragments.

32

Figure 6: Run times for Algorithm 5.6 (ConcurrentFroidurePin) against number of fragments.

5x5 reflexive boolean matrix monoid

160

Time in seconds.

140
120
100
80
60
40
20
12 4

8

16
Number of fragments.

32

Figure 7: Run times for Algorithm 5.6 against number of fragments.
19

