Computing finite commutative semigroups (Q1924511): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 16:11, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computing finite commutative semigroups |
scientific article |
Statements
Computing finite commutative semigroups (English)
0 references
18 June 1997
0 references
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.
0 references
finite totally ordered sets
0 references
binary operations
0 references
weak precedence
0 references
algorithms
0 references
commutative semigroups of order 9
0 references