Two variants of the froidure-pin algorithm for finite semigroups

Julius Jonusas, J. D. Mitchell, M. Pfeiffer

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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 <A> 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 <A>, that has been found using the Froidure-Pin Algorithm, to compute the semigroup <A∪B>. 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 <A∪B> from that for <A>. The second algorithm is a lock-free concurrent version of the Froidure-Pin Algorithm.

Original languageEnglish
Pages (from-to)173-200
Number of pages28
JournalPortugaliae Mathematica
Volume74
Issue number3
DOIs
Publication statusPublished - 8 Feb 2018

Keywords

  • Algorithms
  • Green's relations
  • Monoids
  • Semigroups

Fingerprint

Dive into the research topics of 'Two variants of the froidure-pin algorithm for finite semigroups'. Together they form a unique fingerprint.

Cite this