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