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.

Review text

Summary: 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 \textit{V. Froidure} and \textit{J.-E. Pin} [in: Foundations of computational mathematics. Selected papers of a conference, held at IMPA in Rio de Janeiro, Brazil, January 1997. Berlin: Springer. 112--126 (1997; Zbl 0876.20034)], 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 \(\langle A\rangle\) 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 \(\langle A\rangle\), that has been found using the Froidure-Pin Algorithm, to compute the semigroup \(\langle A\cup B\rangle\). More precisely, we describe the data structure for a finite semigroup \(S\) given by Froidure and Pin [loc. cit.], and how to obtain such a data structure for \(\langle A\cup B\rangle\) from that for \(\langle A\rangle\). 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)