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

Леша доказана. Л е м м а 5. Существует алгоритм, который по данной системе выписывает все её решения Q0 такие, что Qo - > та0 С> - неприводимо. Д о к а з а т е л ь с т в о . Дана система / Вк . (7) ( в „ . ., %к - слова) Докажем, что d(Q ) и m a x {&(&;)■+ : + < tii&k Uisk Пусть t?/2= л ^ с Р , . . По л еш е 2 / <уг , следовательно, =/г C X to - ъ / а ч ) . Из этого неравенства следует, что, т . к д о д а ю быть /ll(d (< 2 )-V fa 1)) « д ( В с ) f ; откуда получаем первое неравенство. Диалогично можно ограничить <? Q r/; = ^ " ;* * £ ,• ( 1 - & У Снова, еоли т0 4 <"/2, . Получаем, что x e c * 2 t/li - 2 S { .-Следовательно, 2 / ц > 2 t/i, - 2 S ; , т .е . t * m A c c iS i+ fl . f*i*k Из полученных неравенств следует, что для системы (7) ре­ шений искомого вида конечное число и можно выписать все подозре­ ваемые на решение косы. Из них можно отобрать те, которые имеют вид 4 ~Х6С? , где С? - неприводимое слово. Для каждой из ос­ тавшихся кос можно проверить, является ли она решенном системы СО. В случае, если / ! , , . . . , fZk - переменные, это можно сделать по л еш е 4. Таким образом, имеет место следующее. По данной системе (1 ) строится конечное множество систем С { г ) . Обозначим входя­ щие в С(г) систош через Q , C { f ) ■={С1>Сл , , ] Каадая система ([ еССО имеет нонечное число решений вндаЛ^С?, где б? - ноириводимо, и эти решения алгоритмически находятся (лемма 5 ). Обозначим эти решения S * 1 .Пусть С\- имеет вид 1 * Л » ^ ~s s ,S c I х'Р* = a ~j s * В^, 122 -