<p>You asked the same question <a href="https://math.stackexchange.com/a/1756306/80190">here</a>
and I answered it. Jean-Eric's algorithm is for computing the elements (among other things) of a semigroup defined by a generating set, and is not related to your question.</p>

CC BY-SA 3.0
2016-04-24T09:03:28.283Z
I know it, there I comented on your answer.
David  Tsaturyan
CC BY-SA 3.0
2016-04-24T21:06:45.497Z
Crossposting the same question on different stackexchange sites is against our site policy.
Lev Reyzin
CC BY-SA 3.0
2016-04-24T07:50:35.010Z
2016-04-24T07:50:35.010Z
2017-04-13T12:19:19.363Z
James Mitchell
<p>Is there any efficient algorithm for computing all semigroups of order n?</p>

<p>I found the following paper which solves a bit different problem.</p>

<ul>
<li>Veronique Froidure and Jean-Eric Pin, "<a href="https://www.irif.univ-paris-diderot.fr/~jep/PDF/Rio.pdf" rel="nofollow">Algorithms for computing finite semigroups</a>"</li>
</ul>

CC BY-SA 3.0
2016-04-23T10:50:55.907Z
What do you mean by efficient? There are exponentially many semigroups, so you cannot do better than exponential time.
Emil Jeřábek
CC BY-SA 3.0
2016-04-23T11:01:22.163Z
I thought like this: So we have n^n^2 binary algebraic structurs of order n, (if consider they're all specified by Cayley's tables A[1],A[2],...A[n^n^2]) is it possible to fix a table A[i] which is a semigroup, can we say for some A[j]...A[k] tables they're semigroups too?
David  Tsaturyan
CC BY-SA 3.0
2016-04-23T11:18:19.800Z
J.E. Pin, one of the authors of the paper, comments here frequently. Maybe you can contact him directly. Please share the answer here.
Martin Berger
CC BY-SA 3.0
2016-04-23T12:04:12.853Z
Regarding finding other semigroups $A[j]$ from a given $A[i]$, any permutation on $\{1,\ldots,n\}$ will give you an isomorphic semigroup. (Or would you consider these the same?)
Klaus Draeger
CC BY-SA 3.0
2016-04-23T12:17:35.513Z
@KlausDraeger You are wrong, If **A[i]** is a semigroup it doesn't mean that any  permutation on {1,…,n} will give us an isomorphic semigroup.
David  Tsaturyan
CC BY-SA 3.0
2016-04-23T12:24:39.590Z
@DavidTsaturyan if $*$ is the operation represented by $A[i]$ and $\pi$ is a permutation, then $\circ$ given by $x\circ y=\pi^{-1}(\pi(x)*\pi(y))$ should again be a semigroup operation. Sorry for leaving out those details.
Klaus Draeger
<ds.algorithms><co.combinatorics><gr.group-theory>
Is there any efficient algorithm for computing all semigroups of order n?
David  Tsaturyan
# Is there any efficient algorithm for computing all semigroups of order n?

(Asked by: username_0 on 2016-04-23)

Is there any efficient algorithm for computing all semigroups of order n?

I found the following paper which solves a bit different problem.

* Veronique Froidure and Jean-Eric Pin, "[Algorithms for computing finite semigroups](https://www.irif.univ-paris-diderot.fr/~jep/PDF/Rio.pdf)"

**Tags:** ds.algorithms, co.combinatorics, gr.group-theory

> **Comments:**
> **username_1**: What do you mean by efficient? There are exponentially many semigroups, so you cannot do better than exponential time.  
> **username_0**: I thought like this: So we have n^n^2 binary algebraic structurs of order n, (if consider they're all specified by Cayley's tables A[1],A[2],...A[n^n^2]) is it possible to fix a table A[i] which is a semigroup, can we say for some A[j]...A[k] tables they're semigroups too?  
> **username_2**: J.E. Pin, one of the authors of the paper, comments here frequently. Maybe you can contact him directly. Please share the answer here.  
> **username_3**: Regarding finding other semigroups $A[j]$ from a given $A[i]$, any permutation on $\{1,\ldots,n\}$ will give you an isomorphic semigroup. (Or would you consider these the same?)  
> **username_0**: @KlausDraeger You are wrong, If **A[i]** is a semigroup it doesn't mean that any  permutation on {1,…,n} will give us an isomorphic semigroup.  
> **username_3**: @DavidTsaturyan if $*$ is the operation represented by $A[i]$ and $\pi$ is a permutation, then $\circ$ given by $x\circ y=\pi^{-1}(\pi(x)*\pi(y))$ should again be a semigroup operation. Sorry for leaving out those details.  

---

## 1 answers

### Answer by username_4 on 2016-04-24. Score: 3

You asked the same question [here](https://math.stackexchange.com/a/1756306/80190)
and I answered it. Jean-Eric's algorithm is for computing the elements (among other things) of a semigroup defined by a generating set, and is not related to your question.

> **Comments:**
> **username_0**: I know it, there I comented on your answer.  
> **username_5**: Crossposting the same question on different stackexchange sites is against our site policy.  

---

