JournalspmVol. 74, No. 3pp. 173–200

Two variants of the Froidure–Pin Algorithm for finite semigroups

  • Julius Jonušas

    Technische Universität Wien, Austria
  • James D. Mitchell

    University of St Andrews, UK
  • Markus Pfeiffer

    University of St Andrews, UK
Two variants of the Froidure–Pin Algorithm for finite semigroups cover

A subscription is required to access this article.

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 UU is any semigroup, and AA is a subset of UU, then we denote by A\langle A\rangle the least subsemigroup of UU containing AA. If BB is any other subset of UU, then, roughly speaking, the first algorithm we present describes how to use any information about A\langle A\rangle, that has been found using the Froidure-Pin Algorithm, to compute the semigroup AB\langle A\cup B\rangle. More precisely, we describe the data structure for a finite semigroup SS given by Froidure and Pin, and how to obtain such a data structure for AB\langle A\cup B\rangle from that for A\langle A\rangle. 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–200

DOI 10.4171/PM/2001