10 A. YU. OLSHANSKII AND M. V. SAPIR

Baumslag-Solitar relations allow us to treat the case of rings, but they cause

the main technical difficulties in the cases of rolls and spirals.

Acknowledgment. The authors are grateful to the referee for many

useful remarks.

2 List of relations

2.1 S'-machines

Here we give the general definition of S-machines (see [01Sa2]). The precise

definition of the S'-machines used in this paper will be given later.

Let Ti,...,Tfc be a collection of groups, T{ — (A^), i = l,...,fc, and the

sets A{ of generators pairwise disjoint. Let % be a set of state letters, disjoint

from UAi. Let A be a set of admissible words of the form qiW\q2...qkWkqk+i

where Wi is a word over some Aj, qi G % U

%~1.

We do not distinguish words over A{ which are equal in the group T{. So

we can view Wi as elements in T{.

Any S-rule r has the following form \k\ — vik^ui,..., kn — vnk'nun}

where u-j,Vj are group words over UA;, kj G X U

%~l.

Every S-rule is

a partial transformation on the set of admissible words. Every admissible

word W in the domain of the S-rule r must have 3C-letters only from the

set

{fc^1,..., k^1}

(not all of these letters may occur, and some of them may

occur more than once). This transformation takes an admissible word W,

and replaces each

k^1

by (vjkjUj)^, freely reduces the resulting word and

then trims maximal prefix and suffix of the resulting word consisting of non-

DC-letters. For example, if W =

fciPifcip2^2"1P3^3 f°r

some words p\,P2,Ps

over UAi (we assume n 3) is in the domain of r, then the result of the ap-

plication of r is the freely reduced form of

k,1u\p\V\kf1u\p2U~2Lk~^

v^p^z^-

Notice that the resulting word must be an admissible word for the S-machine

as well, otherwise W is not in the domain of r.

The inverse rule r

_ 1

is the inverse partial transformation. It has the

form [k[ — •

v^lk\u^1,...,

k'n —

v~lknu~1].

Thus we can view an S-machines as a semigroup of partial transfor-

mations of the set of admissible words. If W is an admissible word of an

S-machine S, and h — riT2...rn is a sequence (word) of rules of S, applicable

to W (that is W is in the domain of the partial map /i), then the result

W1

of

application of h to W is denoted by W o h. The corresponding computation

W,WoTl,Wo Tir2,..., W will be denoted by W • h or W • h = W.

The collection of groups T{ and the set of admissible words form the

hardware of an S-machine. The software of an S-machine is a finite collection

of S-rules closed under taking inverses.