How to check whether arbitrary finite [syntactic] monoid is aperiodic or not? Does there exist an algorithm to decide whether a (finite in my case) syntactic monoid is aperiodic or not? 
By definition, a monoid is aperiodic if for each $x$ from monoid there exists an $n$ with $x^n = x^{n+1}$. 
I can verify if a monoid is aperiodic (i.e. such $n$ exists), but there are difficulties when it is not (at which $n$ can I stop at brute-force?).
I also know the following properties: 


*

*monoid is aperiodic iff its subgroups are trivial

*monoid is aperiodic iff its $H$-relation is trivial


But I don't understand how to find these either. Can you please explain the right way to solve this?
 A: If your monoid contains $N$ elements, at least two of $\{1,\dots,x^N\}$ must be identical (by the pigeonhole principle). Also, if you have $\ell>k$ with $x^k=x^\ell$, the sequence of powers of $x$ which starts at $x^k$ is $\ell-k$-periodic. So if you haven't found an $n$ with $x^n=x^{n+1}$ by the time you reach $n+1=N$, you never will.
That is, if you're using the brute-force approach, you can stop after computing the $N$th power of each element. (I make no promises that this algorithm is remotely optimized — for example, you could stop a lot earlier if you notice that you're already in a cycle, and this also duplicates a lot of work between different values of $x$ — but it is guaranteed to terminate.)
A: If your monoid is given by a finite automaton, you cannot hope in general for a very efficient algorithm, since it is proved in [1] that aperiodicity is $\text{PSPACE}$-complete.
On the other hand, one can test in $O(|A||M|)$-time whether an $A$-generated finite monoid $M$ is aperiodic. For this, you can first compute the right and left Cayley graph of the monoid: the vertices of these graphs are the elements of $M$ and for each $m \in M$ and each generator $a \in A$, there is an edge $m \xrightarrow{a} ma$ for the right Cayley and $m \xrightarrow{a} am$ for the left Cayley graph. The strongly connected components of the right [left] Cayley graph give you the $\mathcal{R}$-classes [$\mathcal{L}$-classes] of $M$. Intersecting 
$\mathcal{R}$-classes and $\mathcal{L}$-classes give you the $\mathcal{H}$-classes and it suffices to check that all of them are trivial.
Moreover, there are a few things that can help you. For instance, a finite monoid is aperiodic if and only if its regular $\mathcal{H}$-classes are trivial (so you don't have to care about nonregular elements). 
If you already have the multiplication table and want to use brute force, you can iteratively compute $x, x^2, x^4, x^{2^k}$ until $2^k \geqslant |M|$ ($\log(M)$ steps) and then check whether $x^{2^k} =  x^{2^k}x$. Not very efficient, but it will work.
[1] S. Cho, D. T. Huynh, Finite-automaton aperiodicity is PSPACE-complete, Theoretical Computer Science 88 (1991) 99–116
