12 A. YU. OLSHANSKII AND M. V. SAPIR
We also define the set of basic letters X which consists of letters Zj where
z G {K, L, P, i?}, j = 1,..., N. Letters from
X~l
are also called basic letters.
There exists a natural map from X U X~l to X U X~~l which forgets indexes
r and i. If z is a basic letter, r E £, i E {1,2,3,4,5} then z(r, i) G X. If
J7 is a word in X and other letters, r E £, i E {1,2,3,4,5} then U(r,i) is
a word obtained from U by replacing every letter z E X by z{r,i). The
parameters r and i in the letter z(r,i) or in the word U(r,i) will be called
the £-coordinate and the ^-coordinate of the word.
The set A of tape letters of the machine S consists of letters a{(z) where
i = l, ...,m, z G X. For every z G X we define ^l(^) as the set of all di(z),
i = 1, ...,m.
Let E be the following word (considered as a cyclic word):
K^^R^-'R^P-'L^KSLSPSRSK^1
K~l
/ ?
- 1
P
_ 1
T
_ 1
(2.2)
Notice that for every basic letter z precisely one of z and z
_ 1
occurs in the
word E. The word E = E(0,1) will be called the hub.
For every z G Xl}X~l by Z- we denote the letter immediately preceding
z in the cyclic word E or in E
_ 1
. This definition is correct because every
basic letter occurs exactly once in the word E or its inverse (see remark
above). If z' Z- then we set z
zf+.
Similarly we define Z- and z+ for
z G X. Notice that for every j = 1,..., iV,
(LJ
and
(Rjh =
Kj
Kilr
Kili
Kj
if j is odd,
if j is even.
if j is odd,
if j is even.
To simplify the notation and avoid extra parentheses, we shall denote {Lj)-
by Lj and (i?j)+ by Kj. We also define A(z"1) for z G X by setting ^ ( z - 1 ) =
A(zJ).
The language of admissible words of the machine S consists of all reduced
words of the form W = yiUiy2U2...ytUtyt+i where yi, ...,yt+i ^
X±:L,
'Ui are
words in A(yi)1 2 = 1,2,..., t, and for every i = 1, 2,..., t, either ^
+
i = (yz)+
or i/i+i =
y~l.
(Here = is the letter-for-letter, or graphical, equality of
words.) The projection of yi...yt+i onto X will be called the base of the
admissible word W. The subword yiuiyi+i is called the yiyi+i-sector of the
admissible word W, i = 1,2 The word u\ is called the inner part of the
yiyi+i-sectov. We assume that the inner part of any zLj-, zPj- or i?j2:-sector
of W and W~l is a positive word (z G X), that is it does not contain a~1
for any a £ A. Notice that if W is an admissible word for S then W~l is an
admissible word as well.
Previous Page Next Page