АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП И ИХ ПРИЛОЖЕНИЙ 1983 г.

^ r n g .- .r ^ , ( 3 ) где hg = Kg. , равная Ф(ф) = 2 а . Слова ввда ( I ) , (3 ) - нетрансфор мы , причем слова вида ( I ) - нечетной длины, слова вида ( 3 ) - четной длины. Подслово 1лф называется левой половиной, подслово r.ig ... ft о. - правой половиной слов ( П , ( 3 ) . Рассмотрим конечное множество слов jt=4,N группы (я- , каждое из которых приведено к виду ( I ) , (2 ) или ( 3 ) . О п р е д е л е н и е 4 . Левая (правая) половина слова называется изолированной в множестве , если ни у одного из слов V j ( £ . = 4 ) множества ({ l? i МЛ .'*) нельзя ш д е- лить Ъ т ) в качестве начального (конечно­ г о ) подслова, то есть i f f * ^ I’ nuSj "• ) » если t * I'nttsi) принадлежат разным сомножителям груп­ пы G О п р е д е л е н и е S СЗ ]. Назовем конечное множест­ во {i7i}i.=T^T слов группы Ст специальным, если оно удовлет­ воряет условиям: 1) левая половина нетрансфорш из множества изолирована в нем; если нетрансформа есть слово четной дли­ ны, то изолированы и левая, и правая половины; 2 ) длину нетрансфорш V\c нельзя уменьшить, умножая слева и справа на слова из подгруппы, порожденной множеством {CWiH*£E \ 5 длину произвольного элемента нельзя уменьшить, умножая на слово V длины мэкьпэ ЦТ^Д принадлежащее подгруппе < > S 3 ) пусть lifc глха . , £ = * 1 , j c n - нетрансформа из множества jtfiJisTJB * ( А >=- 1 ) - подмножество нетранЬформ из множества правая половина которых оканчивается подсловом л ,ц ( f тогда, если подгруппа >лi * « i - ,7wcPrjut ,I. г ,и , = В ,