Eventually H-related sets and systems of equations over finite semigroups and rings

DOI10.1006/JABR.1996.0225MaRDI QIDQ1921916zbMATH OpenOpenAlexFDO

Authors Mark Sapir

Publication date 5 March 1997

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jabr.1996.0225

zbMATH Keywords

\(\mathcal H\)-relationalgorithmsdisjoint subsetsfinite ringsfinite semigroupslinear equations

Mathematics Subject Classification ID

Finite rings and finite-dimensional associative algebras (16P10) Free semigroups, generators and relations, word problems (20M05) General structure theory for semigroups (20M10)

Review text

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.

Recommendations

• Dichotomies in the complexity of solving systems of equations over finite semigroups
• Systems of Equations Satisfied in All Commutative Finite Semigroups
• Identifying solutions to systems of equations in semigroups with finite ideal
• Unifying solutions to systems of equations in finite simple semigroups.
• Identity problems, solvability of equations and unification in varieties of semigroups related to varieties of groups

Cited in

(11)

• Undecidable problems for completely 0-simple semigroups.
• Unifying solutions to systems of equations in finite simple semigroups.
• Identifying solutions to systems of equations in semigroups with finite ideal
• Some undecidable embedding problems for finite semigroups
• Small semigroup related structures with infinite properties
• Potential Divisibility in Finite Semigroups is Undecidable
• A Variety Where the Set of Subalgebras of Finite Simple Algebras is Not Recursive
• Undecidability of Algebras of Binary Relations
• Equations over direct powers of algebraic structures in relational languages
• Minimal signatures with undecidability of representability by binary relations
• Elements of algebraic geometry over a free semilattice

This page was built for publication: Eventually \({\mathcal H}\)-related sets and systems of equations over finite semigroups and rings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1921916)