Алгоритмические проблемы теории групп и полугрупп. 1994 г.

'наименьшее число областей, имеющих не пустое пересечение с С в диаграмме ’Si. Дусть это будут области ^ , Я # , . . . , 2 ^ причем области S)f и 2)т пересекаются с ’¡Т как минимум по ребру. Заметим, что если 2 , д 2 ' п д 2 " ~ е дЯ 'п в р 'л к -'^ п ' „ ~ с’ ¡ j ’ ' вершина М, то А^ не содержит области такой, что вершина является внутренней вершиной пу­ ти дЯГ)<5 . данное замечание справедливо, если Afer заме­ нить на , а А^- - на А ^ . Выделим случаи, отличные от рассмотренных в (О. (а ; Пусть для -Й, , / < у ^ / п , граничащих с с ’ , i(to,)=i(%m)= !l и для всех остальных , /V V ^ , ¿о < /<т , ¡(Ю =Ц . При этом возможны два случая: ( I ) среди областей % содержит ся область ^ , / < ¿< 72 , т ак ая , что д З , П 6 = / Г .^ ' Ъ П П ' - О / , = = * ’ (2) *С содержит области ^ t / < / < /г такие, что д Щ п д » ^ = е ; / ? ^ 4 У, П 6 = Э ^ п & ^ о / . Из приводимости в М областей ^ с ^ с и т .д , аналогично из приводимости $ 1 с , <^г_, с 5^ и т .д . в в первом случае получим, что к областям 2 -^ 3 ) ' я „ 4>ч ’ > ’ < 3 °+ ' в М можно применить Л - преобразование, откуда будет следо­ в а т ь , что область или имеет степень меньше 4 ; во втором случае, выполняя эти же действия, получим, что метка области ^ .-/ или сократима. (б ) Пусть Щ п е * \ § % п ? ^ 0 'л области ^ ^ из выделенной последовательности ЧЯ,-, у * /п / тако вы , что <?Я , / 7 0 * £ ^ 4 д Я ^ п е = О' д%)} /7 6 =У/. пусть ¿(% п )= 2 , /те-и у , 4 у < т , 3 * / < ^ / 2 ,: П е ^ с Щ п б , и наоборот. Тогда из приводимос­ ти областей 4 , с # л г , с Я * , . , . . . . . % с 4 получим, что к областям 2), , , 5^ можно в М применить л -пр е­ образование, из чего будет сл едо ва т ь , что метку в обла­ сти Я 3 можно разбить меньше, чем на 4 ку ска. И, наконец, если предположить, что % о - специальный слой, то проводя аналогичные рассуждения, получим, что М<о тоже является специальным слоем. Лемма доказана. 29