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.
Previous Page Next Page