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

( где СЧ . ^ 1 “ заданные слова, *3- неизвестное) в группе б- ко­ нечного типа указывает, имеет она решение или нет. Существует ал­ горитм, который по всякой системе вида (2 ) указывает образующие конечно порожденной полгруппы Г группы 6- конечного типа и спи­ сок слов Vi ( ...Vo такие, что общее решение системы ( 2 ) описывает - ся формулой вида : У ~ p Vi (6;= , где р - произвольное слово подгруппы Г . Доказательство данной леммы аналогично доказательству леммы 7 [в"\. СЛЕДСТВИЙ. Существует алгоритм, который по всякой системе ви­ да Ач>=тХ(Ч . где A i., fc-teCr* , указывает, имеет она в (^решение или нет. Пусть р и X - две конечно порожденные подполугруппы полугруп­ пы G-+ . ЛЕММА %. Во всякой однородной полугруппе с конечным числом соотношений разрешима проблема вхождения. Доказательство очевидно. В дальнейшем будем рассматривать только конечно порожденные подполугруппы полугруппы 6 г+. Пусть 'р, и St - конечно порожденные подполугруппы полугруппы £+. ТЕОРЕМА 6 . Существует алгоритм , позволяющий установить, сопря жены ли 'р и St в S-i" или нет. ДОКАЗАТЕЛЬСТВО. Пусть Ai, - неприводимая система образующих для р, , Выпишем для каждого ( р= VT*) слова в подполугруппе такие, что D ( . Составим системы урав нений вида: Ыр'А =? г ( з ) Из следствия леммы 2 следует, что существует алгоритм, распоэна - ющий, разрешима или нет любая из систем вида ( 3 ). Возможны случаи: 1 . Ни одна из систем вида (3 ) решения не имеет. Следовательно, подполугруппы и X полугруппы G rне сопряжены. 2 . Одна из систем вида (3) имеет решение. Пусть таково, что ° Ц р = li г'] и {w y , . . - неприводимая система образующих для . По лемме Ц, проблема вхождения в 6 * разрешима.Для каждого слова О»-С*) выясним, входит ли оно в подполугруппу^ полугруппы £ 4 порожденную , ■■■ » или нет. а) Если для любого jj ( -j =иТ*- ) , то и SC сопряжены. б) Если существует g С 8 ~ ' Гк > такое, что > та пункт 2 про веряется относительно других систем, в) Если для любой системы вида (3 ) выполнено условие б ) , т о £ и'Д не ооп ряжены 159