Two variants of the Froidure-Pin algorithm for finite semigroups

DOI10.4171/PM/2001MaRDI QIDQ2413194zbMATH OpenOpenAlexWikidataFDO

Authors J. Jonušas, J. D. Mitchell, Markus Pfeiffer

Publication date 9 April 2018

Published in Portugaliae Mathematica. Nova Série (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.04084

zbMATH Keywords

algorithmsGreen's relationsmonoidssemigroups

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to group theory (20-04) Free semigroups, generators and relations, word problems (20M05) General structure theory for semigroups (20M10)

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

Recommendations

• Algorithms for computing finite semigroups
• Computing finite semigroups
• Computing transformation semigroups
• Computing automorphisms of semigroups.
• Computing maximal subsemigroups of a finite semigroup

Cited in

(3)

• Computing maximal subsemigroups of a finite semigroup
• Random ubiquitous transformation semigroups
• Algorithms for computing finite semigroups

This page was built for publication: Two variants of the Froidure-Pin algorithm for finite semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2413194)