A subscription is required to access this article.
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 is any semigroup, and is a subset of , then we denote by the least subsemigroup of containing . If is any other subset of , then, roughly speaking, the first algorithm we present describes how to use any information about , that has been found using the Froidure-Pin Algorithm, to compute the semigroup . More precisely, we describe the data structure for a finite semigroup given by Froidure and Pin, and how to obtain such a data structure for from that for . The second algorithm is a lock-free concurrent version of the Froidure-Pin Algorithm.
Cite this article
Julius Jonušas, James D. Mitchell, Markus Pfeiffer, Two variants of the Froidure–Pin Algorithm for finite semigroups. Port. Math. 74 (2017), no. 3, pp. 173–200DOI 10.4171/PM/2001