Title: Two variants of the Froiduire-Pin Algorithm for finite semigroups,
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
$\langle A\rangle$ 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 $\langle A\rangle$, that has been
found using the Froidure-Pin Algorithm, to compute the semigroup $\langle A\cup
B\rangle$. 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 $\langle A\cup B\rangle$ from that for $\langle A\rangle$. The
second algorithm is a lock-free concurrent version of the Froidure-Pin
Algorithm.