EVENTUALLY H-RELATED SETS AND SYSTEMS OF EQUATIONS OVER FINITE-SEMIGROUPS AND RINGS

I prove that given a finite semigroup or finite associative ring S and a system S of equations of the form ax = b or xa = b, where a, b is a n element of S, x is an unknown, it is algorithmically impossible to d ecide whether or not Sigma is solvable over S, that is, whether or not there exists a bigger semigroup or ring (resp. finite semigroup, fini te ring) T>S such that Sigma has a solution in T. The proof employs th e unsolvability of the uniform word problem in the case of groups (Nov ikov) and in the class of finite groups (Slobodskoii) and the so-calle d split systems. (C) 1996 Academic Press, Inc.