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

I: ^Н М ".!Г'^ М И П iy-'\ A 'i •'•■',4 - I ■’ Элементы множества K.(w) обозначены через Ke(w),...,Ke_l(w), а кольц, вые диаграммы, принадлежащие множеству AV(vv), будем называть представ> телами K^w). Говоря о представителе элемента будем обозначать это , ■ Г4'., представитель через Ki(w). Определение 2.2. Будем говорить, что множество K(w) определено, ecjii последовательность диаграмм M 0 (w) бесконечна. В противном случае K(w) н ; определено. Будем считать, что элементы множества А'(и’) пронумерованы (пс modE ) в порядке следования их представителей в диаграммах из M0(w). Ниже, пока не доказана лемма 2.10, будем считать, что Af(vv) определено Метками представителей элементов из AT( vv ) являются степени слов w 0 = w 2 , vv 1 ,..., h '£;_1. Рассмотрим множество М( w) всех приведенных диаграмм сопряженности слов и" со словом v2m. Естественно, M eM (w ). Из минимальности чисел jnj,|w[ следует, что если М 'е M(w) - диаграмма сопряженности слов w”,v2” , то из М 'нельзя вырезать поддиаграмму М " , замкнув которую в кольцо, получим диаграмму сопряженности слов w "1 ,v2” при Ы < п\,т. < т . Действительно, предположив противное, наклеим на границу М "с мет­ кой мЛдиаграмму, склеенную из менее, чем Е слоев из множества K(w)\ по­ лучим диаграмму М '" сопряженности слов w2”' = ,v2"' при |и,|< и, от, <\т\, что противоречит выбору чисел п,т. Пусть А /0 - диаграмма из M{w) такая, что М0 = min М '. Обозначим граничные метки М0 через wj,v2". Очевидно, диаграмма М0 простая: если М0- С-А-слойная при к> 0, то сняв с М 0 к -слойную поддиаграмму М 0 . получим диаграмму М~0 е M(w), такую, что 'М а\< |A/ 0 j. 44