Eventually \({\mathcal H}\)-related sets and systems of equations over finite semigroups and rings (Q1921916): Difference between revisions

It is shown that there exists no algorithm which, for any given finite semigroup \(S\) and disjoint subsets \(A\) and \(B\) of \(S\), decides whether or not there exists a (finite) oversemigroup \(T\) of \(S\) such that \(A\subseteq H_1\) and \(B\subseteq H_2\) for some \(\mathcal H\)-classes \(H_1\) and \(H_2\) of \(T\). As a consequence there is no algorithm which, for any finite semigroup \(S\) and a finite set \(\Sigma\) of equations each one of the form \(ax=b\) or \(xa=b\), \(a,b\in S\), decides whether or not \(\Sigma\) is solvable in some (finite) oversemigroup of \(S\). Such an algorithm exists however in the case where the sets \(\Sigma\) are allowed only to consist of equations of the type \(ax=b\), or only of the type \(xa=b\). Similar results hold for finite rings.