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

типов дисков из М0 по /^^-классификации следует совпадение их типов по К (и’)-классификации. Пусть К {,Кг - длинные диски в М0 первого и второго типов, соответст- венно. Рассмотрим элемент из AT(w), имеющий представитель с таким же осно­ ванием из р областей, что и Kf" - слой диска АГ,. Рассмотрим диаграмму JV, . представитель того же элемента, одна из меток которого равна w", а другая - и>”. Склеим диаграммы Л /0 и Nt по границам с меткой w". Приведенную диаграмму, полученную из М0 и N{ удалением областей из дисков первого ти­ па, сокращающихся с областями из N ,, обозначим через /V,. Граничные метки N[ равны н>",г 2" . На простые пути, соединявшие дис­ ки в М 0, в Nt наклеены диски второго типа. Диски второго типа из М0 стали в /У, длиннее и толще, а диски первого типа - короче и тоньше, и, возможно, распались на более короткие диски первого типа. Далее наклеиваем на N[ по границе с меткой и>" представитель N2 эле­ мента из Af(w), имеющий общее со слоем К?' основание, и одну из граничных меток - слово w". Удаляя из диаграммы N[ п Ыг все сократимые пары облас­ тей, получаем диаграмму Ыг с граничными метками w",v~2m. На N ’2 наклеива­ ем диаграмму N }, и так далее. Диаграмма N, при / >1 имеет метки w”,v'2” . В качестве диаграмм N , из K(w) берутся представители элементов с последовательно растущими номера­ ми, так как К, - диск первого типа. Таким образом, на каждом шаге применя­ ются преобразования . Указанные преобразования продолжаем до тех пор, пока не получим диа­ грамму /V,, в которой нет дисков первого типа, а есть лишь диски второго типа (легко проверить, что полученная диаграмма является простой). 60