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

Доказательство. Рассмотрим слой К„ . Изменив при необходимости ну­ мерацию областей, можем считать, что /(ц“)= 3 . Рассмотрим циклическую пе­ рестановку w’ слова w такую, что ф(д£>° п о ) - начало слова w*. Рассмотрим поддиаграмму Ц =D° и . , . и О ' с минимальным г такую, что слово и>’ являет­ ся подсловом в слове и, в ф(д£, п сг). 1) Предположим, что w= ul . Докажем, что ф(дО° п а) * ф{дО',ы п о), }. M i'A ','. HNHl ф{В^)шф(дй^). a) Пусть |ф(зд°+. П о) >1. Приклеим область D,0 к области О г°+1 по гра- ■ и КО нице а . Если |ф(ЭЕ>,° п о) < ф((5 /)°+1 ) п о) , то либо ф(зд° n o)j = 1 , и |ф(зд° )| < 6 , либо ф(ал|°)=ф(эд0.,), и, наклеив область D°+l на области D°, D° по границе о , приходим к выводу, что в слове ф(ао“) есть свободное сокращение. Значит, случай |ф(э£>,° п °)< ф(ао^,) По| невозможен. ••qriO-J ....' Случай ф(ао,° п о ) > ф(аД°+| п о ) рассматривается аналогично предыду- щему. ■ФН;. Iи >. .‘Ж /\ и Остается последняя возможность: ф(5/?,° п о)= ф(эд°+, п о), причем пт • ■ ф И И эо :+1). •' - • \ *- . b ) Пусть ф(<ЗО,0+| п о ) = 1 . Если |ф(аД°+| п о ) > 1ф(Э£>,° п о ) , то |ф(ао,° п о | = 1 , и ф(дО,°) <6. V' r' • •> ■ ’V )Vw Предположим, что ф(<ЭЦ° п ^)>!Ф(ая °+1 п о ) . Наклеим область D° на А°н по а ■ Из леммы 1.3. следует, что !|ф(ао ”т2 п о) > 1. Если !Ф(ао,0 п о ) <1фп;+1иао„°+2 ) п о ) , т о ! ф(эо,° п о ) < 2 , ф(ао,°)< 6 . 32