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

...... ^ W V 73 Таким образом, nepes конечное число догов множество d tfl будет представлено в виде дерева-разбиения на подмножества,то есть такого разбиения, которому соответствует дерево-граф , если каждому подмножеству А &9_**ы 9ьър-- ■ ftp,#. tP поставить в соответствие вершину, а каждому адову ■■ , нумерующему подмножество А * . ребро,соеди- .нящее соответствующие подмножествам ■ Заметим, что слово t ei9 t* & ! 9 i4 ip - & 9 i r # , нумерующее подмножество A > является .подсло­ вом правой половины либо совпадает с правой половиной некото­ рой нетрансформы У £ , £ = ± f , либо является конечным под­ словом правого крыла, либо правым крылом трансформ некоторой подгруппы (Jllij) , принадлежащей ряду (1 9 ). Построенное дерево-граф , соответствующий слову и г , будем обозначать . Заметим, что если в слове и г р - 0 и B¥ * f t 8, ¥U t ; если €, = - / , и В, & U-/ , если £ ,~ / , то при построении выделяем в качестве кулевой вершины вершину, соответствующую подмножеству А 0 , содержащему подгруппу (М ^ )= А и , * если среди п о в р у т ! ряда (6) содержится т а к а я , в противном случае Ао считаем пуотым. Построим алгоштм OL укорачивания длины произвольного слова и г с помощью слов подгруппы д о ( Ж , Ю. Допустим, что через с шагов слово и г мы преобразовали в слово зкйй же длины и г ' : „ и г ' - г % #»■ ':.. . . . ( ? % > где слово t eix„], * 4 t? - нумерует подмножество O if. Допустим, что множеству принадле­ жит подгруппа „ i ? r £iA Sj t £% . . ъ * р . I . Пусть t l+1 — £/: , тогда проверяв!- справедливость соотношения - 3? -