THE CONJUGACY PROBLEM AND HIGMAN EMBEDDINGS 13

By definition, all X-letters in an admissible word have the same £-

coordinates and ^-coordinates. Notice that X(r, i) is an admissible word

for every r, i.

Two admissible words VK, W are considered equal if W = W.

2.4 Notation

In this paper, the 5-rules will have a specific form which allows us to simplify

the notation. In every rule [fci — vik'-yUi,..., kn —

vnkfnun],

the projections k{

and k[ on % will be always the same, the £-coordinates and the O-coordinates

of all state letters fci,..., kn (resp. k[,..., k'n) will be the same. In addition,

each ui (resp. V{) will contain only letters from A{ki) (resp. A((ki)-)),

i = l,..., n.

For every word W in the alphabet {ai,..., a^ } and every k G 3C, VF(fc) will

denote the word obtained from VF by substitution a^ — » ai(fc), i = 1,..., m.

In any expressions like v/cu where i; is a word in yi(/c_), ix is a word in

A(k), k G 3C, we shall not mention what alphabets these

wrords

are written

in. For example the notation

aiPja~l

means

ai(Lj)Pjai(Pj)"1,

that is the

two a{ are brothers taken from different alphabets.

Thus in order to simplify notation, we shall write a rule r of the S-

machines S in the form

[fci —• vikiui,...,kn —• vnknun;r —• r\w — a;']

where k{ G 3C, ^ are words in yi((/^)_), ^ are words in A(k{). We shall

denote V{ by v(r((fci)_)), ^ by uT(kt).

Some of the arrows in a rule r can have the form k{—. This means that

the rule r can be applied to an admissible word W only if for every kiky-

sector and every /^//(fci)+-sector in W, its inner part is the empty word, and

ki' — (fci)+j ^ " = h (i.e. £v 7^ A:"1 and kyi ^ (ki)^1). We shall say that in

this case the ki(k{)^-sectors are locked by the rule and the rule locks these

sectors. If /c/c+-sectors are locked by the rule, u(k) and v(k) must be empty.

Thus if r locks fc/c+-sectors then r _ 1 locks these sectors as well.

Let us expand the definition of ur(k),vT(k-) to the base letters not oc-

curring in the rule by setting that in this case uT{k) and vT(k-) are empty.

Thus with every rule r and every k G % we associate two words

over A: uT(k) and vT(k). W e expand this definition to k G

%~x

by

saying that vT(k~1) = izr(fc)_1, uT{k~l) = vT(k-)~l.

By definition, to apply the rule r = [z\ — v\Z\U\, ...,zs — vszsus\r —»

r;,u;

— » u/] to an admissible word VK = yiW\y2-.-Wkyk+i means replacing

each j/i(r, CJ) by viy^r'' ,u')ui, reducing the resulting word, and trimming the

prefix i;T((2/i)_) from the beginning and the suffix uT(yk+i) from the end of

the resulting word. (Notice that t^ is non-empty if ^ = 2 / ^ , and therefore

yi(rf,ujf)

will not cancel with yi+i(r' ,u') in the resulting word, because the