АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1981 г.

Итак, нужно установить, пусто или нет пересечение •S,H,Hs2 H2 f ) . .Я ^ Н д , , где S i ^ G , i= TJV . В общем слу­ чае s( e HL , если же H i , то можно считать = / (кл асс смежности, совпадающий с Н( ) . Очевидно, поставленная зада­ ча эквивалентна задаче о пересечении £4 н,пфан2а... /7#*. о) Обозначит.!: S jJ S i-ty i . Если пересечение (9) це пусто, то най­ дутся такие h ^ H i , что выполняются равенства: У ^ 1 =Уа^я=--~Ул>-1h tf. c~y--v- Запишем каждое /г,- в бг - символах соответствующей подгруппы = у яи а \1 ) и (:г>( 2 ) .., U (2)CL s )= = u ^ o u ^ t e ) . . . (10) = ЦоЧЩ(2> 9ЦУ i ( n Последняя строка дает несократимую запись слова tr в группе G . у 0 - начально^поделовр слова V , U tf0)= /n cu {L (ft)\ Обозначал R^=.\H(0U W MU i * i \ , i - T / f , где д г д а , если jf 'e lV w , Л ■- некоторый символ. Обозначил также через Т ‘ множество всех тш о в трансформ, содержащихся в W a \ пополнен­ ное сшволом . Соотношения (10) определяют следующее отображение: v ' ’ (П ) W ^ Z ^ n ( ( R a)*Z )*T»(R (0-*Z)X где Z = iO r tr 2 , . \ По лемме 2 каждый слог из последней строчки (10) ооразо- ван элементами трах соседили символов, то есть 9 Ц ) - Х и)Ц ^ - х ( Л)у (У>2 СЮ Тогда отображение ( I I ) определяет функцию: х ч у - ш н м ’ ц » , t mw . Т « Ш г .. - I l l -