# Portugaliae Mathematica

Full-Text PDF (1693 KB) | Metadata | Table of Contents | PM summary

**Volume 74, Issue 3, 2017, pp. 173–200**

**DOI: 10.4171/PM/2001**

Published online: 2018-02-08

Two variants of the Froidure–Pin Algorithm for finite semigroups

Julius Jonušas^{[1]}, James D. Mitchell

^{[2]}and Markus Pfeiffer

^{[3]}(1) Technische Universität Wien, Austria

(2) University of St Andrews, UK

(3) University of St Andrews, UK

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.

*Keywords: *Semigroups, monoids, algorithms, Green’s relations

Jonušas Julius, Mitchell James, Pfeiffer Markus: Two variants of the Froidure–Pin Algorithm for finite semigroups. *Port. Math.* 74 (2017), 173-200. doi: 10.4171/PM/2001