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

o 0: 4>(cr 0 )= w” п копий R1=u rMR f,j = 1,...,и диаграммы R так, чтобы для ко­ пий R {,j =\,...,n области D, выполнялось условие: фи\дЯ( п<т0) - начало слова w* (здесь для удобства дальнейших построений копии областей обозначаются теми же буквами, что и содержащие их диаграммы, но с двумя индексами, то­ гда как копии самих диаграмм имеют лишь один индекс). Зафиксируем 2 п вершин на а 0: Л,, Вs - начало и конец пути dRj r \ c a, j =\,...,п. К диаграмме А/, по границе сг 0 приклеим «копий DJr J =1,..,,п так, чтобы dDJr о ЭЛ/,, = йу (здесь копии области D, обозначены че­ рез D /, поскольку они не принадлежат диаграммам R ) ). Получим диаграмму Мг : дМ2 = ст, и т ,. Пусть =?т, ndRj, j =\ ....и. Построим диаграмму М}, наклеив на т, зер­ кальные копии Т' = и ^Г / поддиаграмм = по участкам у, границы т,. 0Л / 3 = а, и т2. Из диаграммы Л /3 построим диаграмму А/4, наклеив на т 2 по участкам S j = t 2 n d T J зеркальные копии S J = uJ’j/iS'/, j = поддиаграмм Т ‘ ; дМ4 = о, и т3. Заметим, что при всех j = поддиаграммы RJ,T J,S J имеют общие вершины: Aj,Br Более того, вершина В. является общей для областей DJr ,RJr^,Tj_y,SjA. Из построения ясно, что область D/ можно склеить с обла­ стью £/_, вдоль пути с меткой ф 0 (3D, n 3D, ,) и началом в вершине BJ. Так и поступим при всех j = 1 , а вдоль ребер = 3D/ n dR{*v сделаем разрезы, после чего получим диаграмму Ms с границей ЭЛ *5 =<т 0 ит4:фГт 4) ^ (¥Р, D ,) 1 о 0 ) Г =w?. В ней области О/ имеют одно ребро на <т 0 и четыре ребра на г4. Заме­ тим, что . 66