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

Рассмотрим диаграмму М, с дМ = у 8 , где <р(у), q>( 8 )'*eG\»*, М содержит простые области. Допустим в М есть область D такая, что dD п у - несвязное множество, и пусть поддиаграмма М\ в Мс границей дМ\ =У\ 5,, где Ш\ п у = yi, 5М| г» 3D = Si такова, что для любой области D ’eM , из того, что cD Угу, * 0 , следует, что ЭО'г^у, - связное множество. Поэтому всякая область D' с М, и dD’n y Ф 0 является простой в М Пусть А/| содержит область Д>, для которой имеют место следующие соотношения: ЭД п 5Л/| = y’i 8 ’ь где у. = У’2у’ь 6, = б’, 64, a w , 8*, /. I/ | - IS’I- 1 . !г’>1= 2, то есть i(D0) = 1 в АД Тогда делящие точки D 0 в полугруппе будет соответ­ ствовать переходу от положительного слова <P(Y) = ф(УоУ’. У’г) = <P(Yo) ф(у’0 ф Ы к положительному слову <р(уо) ф(5’| /) ф(Уг). и в силу индуктивного предполо­ жения теорема 2 справедлива. Пусть М | не содержит областей указанного выше вида, тогда она не со­ держит деновских областей, поэтому М\ содержит по меньшей мере две непе- ресекающиеся полосы. Следовательно М\ содержит область Д , dD\ n dMi = ЗД п у, /(Д ) = 2 и ЗД = (dD i n у) 5|, |5i| = 2, |ЭД n y| = 2, поэтому ф( 6 |) 'еС*а» и делящие точки Д принадлежат у. Получили выше рас­ смотренный случай. *с' Рассмотрим случай, когда в М имеются области не являющиеся простыми и пересекаются одновременно с у и 6 . выделим в М две такие области D, Д , между которыми заключена поддиаграмма Г, ЗГ= yt %\ Si x ’ i . гДе а Г п у - у ,, д Г п 6 = 6 ,. д Г п dD’= х ’ь дГ n 3D = Xi. IXij = 1x4 = 2- Тогда каждая граничная область из D u T u D ’, отличная отD ,D ’ являет­ ся простой. В этом случае йдоль у в Л содержится граничная областьД с /(Д) = 2 в Л/ и <?(ЗД г\у)е(?аь, ф(ЭД\(ЭД п у ))-' eG*ab. Как в предыдущем случае, получили, что делящие точки Д принадлежат у. Допустим, что в М, указанных областей Д D ’нет, и пусть каждая граничная область М — простая, и М не содержит деновских областей, тогда М содержит 145