Eventually \({\mathcal H}\)-related sets and systems of equations over finite semigroups and rings (Q1921916)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Eventually \({\mathcal H}\)-related sets and systems of equations over finite semigroups and rings |
scientific article |
Statements
Eventually \({\mathcal H}\)-related sets and systems of equations over finite semigroups and rings (English)
0 references
5 March 1997
0 references
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.
0 references
linear equations
0 references
\(\mathcal H\)-relation
0 references
finite semigroups
0 references
disjoint subsets
0 references
algorithms
0 references
finite rings
0 references