Projects per year
Abstract
In this paper, we present two algorithms based on the FroidurePin 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 FroidurePin 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 lockfree concurrent version of the FroidurePin Algorithm.
Original language  English 

Pages (fromto)  173200 
Number of pages  28 
Journal  Portugaliae Mathematica 
Volume  74 
Issue number  3 
DOIs  
Publication status  Published  8 Feb 2018 
Keywords
 Algorithms
 Green's relations
 Monoids
 Semigroups
Fingerprint
Dive into the research topics of 'Two variants of the froidurepin algorithm for finite semigroups'. Together they form a unique fingerprint.Projects
 1 Finished
Datasets

libsemigroups  C++ library for semigroups and monoids
Jonusas, J. (Contributor), Mitchell, J. D. (Creator) & Young, M. (Creator), GitHub, 2 Oct 2017
https://jamesdmitchell.github.io/libsemigroups/index.html
Dataset: Software