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

понятий, часто используемых в данной работе. ОПВДШПМШ I . L53. (Сигнализирующая функция времени). t (П) - m.CL3L t ( Р ) IPI &п. i c P ) равно числу тактов для яереработки слова Р во внеш­ нем алфавите S МТ от начальной конфигурации до заключитель­ ной, если процесс переработки с л о т Р конечен, и не опреде­ лено в противном случае. Разрешимость проблемы тождества слов и сопряженности в классе К ( J o доказана геометрическим методом. Доказательст­ во этих результатов приводится в [ 6 1 . Линдон я Щупп рассмат­ ривают отображения [ р , удовлетворяющие уравнению 1 + ±_ - 1 р Ч 2 Целочисленными решениями являются пары ( 3 , 6 ) , ( 4 , 4 ) , ( 6 , 3 ) . ОПРЕДЕЛЕНИЕ 2 . Пусть R -симметризованное подмножество свободной группы F с данным'базисом.. Если R - , R^ <=А- невзаимнообратш и R i 's : S c 1 , Rj. , тогда 6 назы­ вается частью относительно множества R . Знак х обозначает графическое равенство в группе Р , Условие С е р ) : ни один элемент из R не является про­ изведением менее, чем р частей ( р - натуральное число). Условие С '( Л ) : если R . e R , f t . i t 6 с , где 6 - ч а с т ь , тогда [i&'> < x l ( R - L) , i d ) обозначает длину олова в об­ разующих символах группы. f ^ __ Условие CVJC) . влечет условие С е р ) дья р - - / . Условие Т ^ > : nwдгь 3 ^ /г ^ . Предположим Я,,— элементы множества R . Последовательные элементы невьакмнообраткые. Тогда по крайней мере одно из произведений * л . Л - приводится без сокращений. ОПРЕДЕЛЕНИЕ 3 . Последовательность сопряжений элементов R С . . . , * называется минимальной R последовательности; если произведение С1- .■сп нельзя написать как произведение меньшего числа, чем п сопряжений элементов R . В настоящей работе мы используем полученные ранее оценки сигнализирующей функции времени L r>1, а именно лем.му 1 и 2 . - 4 -