 QUICK SEARCH:

The EMS Publishing House is now EMS Press and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

# 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, James D. Mitchell and Markus Pfeiffer

(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