✦ LIBER ✦
Eventually H-Related Sets and Systems of Equations over Finite Semigroups and Rings
✍ Scribed by M.V. Sapir
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 158 KB
- Volume
- 183
- Category
- Article
- ISSN
- 0021-8693
No coin nor oath required. For personal study only.
✦ Synopsis
I prove that given a finite semigroup or finite associative ring S and a system ⌺ of equations of the form ax s b or xa s b, where a, b g S, x is an unknown, it is algorithmically impossible to decide whether or not ⌺ is solvable over S, that is, Ž whether or not there exists a bigger semigroup or ring resp. finite semigroup, . finite ring T ) S such that ⌺ has a solution in T. The proof employs the Ž . unsolvability of the uniform word problem in the case of groups Novikov and in Ž . the class of finite groups Slobodskoii and the so-called split systems.