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

Если \ф(дО? п ст) > |^((0D“., и aD,°,;) пст)|, то либо |ф(эд °,2 п а ) =1, что про­ тиворечит лемме 1.3, либо в слове ф(гЮ^2) есть свободное сокращение. Зна­ чит, ф(ЗД° о.о) = ф(эД°+) п о ) , и ф(зД°)= ф(оД°и ). Пусть при } = 0 *-1 ф{дО,')=р;,р1гр1,р1,, где pl: = ф(зп/ n c j р/з = (3D/ n a JU). Докажем, что р “4 =р,°+|.4, и что ( i{dD° п а )ш ф (д й ^ п а ). Через j M( d ) будем обозначать число граничных ребер области D в диа­ фамме М . Если j{ p l )> 1, и у (д °,2 )> 1, то, как и для областей Д°, D°+,, доказываем, что ф(зД 2 )= ф(дД °г2 )ф(зД° n а )н ф(ЗД 0,2 п о). Предположим, что Ip,0*! < р,°, 14 1. Рассмотрим область D<zKa , содержащую ребра из D°,D°. Из сделанного предположения о длине слова р ,°4 и из совпадения меток ,Л- Y ... . областей Д° и Д°+|, D" и Д °+2 следует, что в слове ф(ЭЕ>) есть свободное со­ кращение, что невозможно. Если же в диафамме М всего один слой, то в слове ф(сг,) есть свободное сокращение, что невозможно в силу циклической R, R -несократимости фаничных меток диафаммы М . Аналогично доказывается, что неравенство р ,°4 > р°+]4! приводит к про­ тиворечию. Таким образом, р°4 = р “+|4!. Предположим, что j M (д° )= \ ,j 4 (д °.2 ) = 1. то есть <w(o°)=<w( d °+2) = 5 . Рассмотрим кольцевую диафамму . Разрезав ее двумя способами: по ребру 3D,° n3D° и по ребру ЭД °+1 г\ЗД°+2, получим две односвязные диафаммы: К, и Кг^ . Области, входящие в эти диафаммы, будем обозначать так же, как и в диафамме Кя . 33