THE CONJUGACY PROBLEM AND HIGMAN EMBEDDINGS 5
following relations in Z: 9~lqOT = uqv, 0Ta a6T for every a E Al)Y (the
letters 0
r
, corresponding to the rules of M are added to the generating set).
In this case the words i^, P[ are of length 1, and are equal to 6T.
The words P and
Pf
contain the history of our computation, because Pi
and P[ correspond to 5-rules applied during the computation. The words
T\ and Tm are labels of the bottom and the top paths of the trapezium.
If the set of relations Z is chosen carefully (and there are very many ways
of doing this, see [SBR, BORS, 01Sa2, OlSal, 01Sa3]), then the converse is
also true:
Condition 1. If there exists a trapezium with the top labelled by I \ ,
the bottom labelled by WQ and the sides labelled by words over O (the set
of all 8T) then T\ is admissible and the labels of the sides correspond to the
history of an accepting computation.
Thus the word PT^P'^W^1 can be written on the boundary of a
trapezium if and only if the word T\ is accepted.
The next step is to consider T V 1 copies of our trapezium with labels
taken from different alphabets. For technical reasons (similar to the hyper-
bolic graphs argument in [SBR], [012], [BORS]) we need T V to be even and
large enough (say, N 8). Let us choose disjoint alphabets in different
copies of the trapezium. Then we can glue two copies of the trapezium by
using a special letter k which conjugates letters from the right side of the
first trapezium with letters from the left side of the mirror image of another
copy (Figure 3):
1 *
P'!\
1 _
'
"* 1
PI
_ 4 1
Ti k ^
Figure 3.
(Notice that if P and P' are copies of each other then we can also glue
the right side of one trapezium to the left side of another without taking
mirror images.) Of course the conjugacy relations involving letter k should
be added into the set of group relations Z.
Previous Page Next Page