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

множеством. Тогда И имеет единственное неприводимое пород, дающее множество и существует алгоритм, строящий это множеств ДОКАЗАТЕЛЬСТВО. Пусть Н порождается мно. ’ жеством i t - { Щ % е } . Множество U можно считать не. приводимым ("иначе, пользуясь разрешшлостью проблемы вхождения можно эффективно сделать его таким) , Пусть V - I v<, t Иг, - ] - произвольное неприводимое порождающее множество для Н . Покажем, что V - U- ( соответствующие слова из ^ и ^ не обязаны быть графически равными, но равны в полугруппе П ) , Рассмотрим произвольный элемент VL , Так как И порож­ дает подполугруппу Н , то К - • В свою очередь, каждый элемент из ЬС тоже выражается через элементы из V : U -i; - . . . i Таким образом, из двух последних равенств имеем % ?. ^ Щ ■ (10) Если V{ не входит в правую ч асть ( 1 0 ) , то получаем противо­ речие с неприводимостью V . Если же входит, то на самом деле К , ••• К р - К • иначе получим противоречие с конечнос­ тью множества равных слов в П . Можно счи тать, что среди слов v i f нет пустых, иначе их можно просто удалит; из последних равен ств. Тогда р> = / и , следовательно, /■ - К ; . Таким образом, VL € U . Аналогии»! получаем, что любой f V и поэтому U. - V . Лемма до­ к азан а. ДОКАЗАТЕЛЬСТВО теоремы 2 . Множество tC - - I К *, Щ \ порождающих подполугруппы Н можно считать неприводимым (лемма 5 ) . Н свободна тогда и только тогда, когда 1C является множеством свободных порождающих. Поэто­ му для выяснения вопроса, свободна ли И ,' йадо проверить, существуют ли нетривиальные соотношения между элементами мно­ ж ества i t . Под нетривиальными понимаются соотношения вида I I (11 где либо a ) t * /> ; либо 6 J для некоторого $ U t £ Причем, если имеется соотношение вида а ) , то оно должно удов-1 льтворять и условию б ) при некотором S , иначе получим про­ тиворечие со следствием 1 . Поэтому можно ограничиться рассмо-) трением случая б ) . Обозначим 00