Computing finite commutative semigroups
type: Item
instance of: scholarly article
title: Computing finite commutative semigroups
zbMATH Open document ID: 0864.20034
DOI: 10.1007/BF02574129
author: Pierre Antoine Grillet
published in: Semigroup Forum
publication date: 1997-06-18T00:00:00Z
full work available at URL: https://eudml.org/doc/135478
review text: The problem is how to list all distinct (not isomorphic or antiisomorphic) semigroups of fixed order \(n\). Let \(S\) be a finite totally ordered set. All binary operations on \(S\) can be totally ordered lexicographically. Let \(m':S\times S\to S\) and \(m'':S\times S\to S\). Define \(m'<m''\) if there is \(a,b\in S\) satisfying the following: \(m'(x,y)=m''(x,y)\) if \(x<a\); \(m'(a,y)=m''(a,y)\) for all \(y<b\) and \(m'(a,b)<m''(a,b)\). For any permutation \(\sigma\) of \(S\), define \(m^\sigma:S\times S\to S\) by \(m^\sigma(x,y)=\sigma^{-1}m(\sigma x,\sigma y)\) for all \(x,y\in S\). If \(m^\sigma\geq m\) for all permutations \(\sigma\) of \(S\), then \(S\) is said to have precedence. If \(m^r\geq m\) only for all transpositions \(r\) of \(S\), then \(S\) is said to have weak precedence. If \(S\) has precedence, equivalently, there is no permutation \(\sigma\) with \(m^\sigma<m\), then we add a semigroup \((S,m)\) to the list since it is not isomorphic to any of the previous semigroups. Assume that \(S\) has weak precedence. When does \(S\setminus\{a\}\) having precedence imply \(S\) having precedence? The criteria are given in the various cases, and also the improved actual algorithm is given. Finally as an application the author classifies 11,545,843 commutative semigroups of order 9.
Mathematics Subject Classification ID: 20M14
Mathematics Subject Classification ID: 20-04
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M20
zbMATH DE Number: 936962
zbMATH Keywords: finite totally ordered sets
zbMATH Keywords: binary operations
zbMATH Keywords: weak precedence
zbMATH Keywords: algorithms
zbMATH Keywords: commutative semigroups of order 9
reviewed by: Takayuki Tamura
MaRDI profile type: Publication
cites work: SWAC Computes 126 Distinct Semigroups of Order 4
cites work: Die Halbgruppen der Ordnungen \(\leq 7\)
cites work: Semigroups of order \(8\)
cites work: Q5831351
cites work: Q5850543
OpenAlex ID: W2073131509
description: scientific article; zbMATH DE number 936962