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

УДК 519.4 В.Н. Безверхний, А.Е. Устян РЕШЕНИЕ ПРОБЛЕМЫ СОПРЯЖЕННОСТИ СЛОВ В МОНОИДАХ АРТИНА БОЛЬШОГО ТИПА1 : VlTfj . Группа Артина - это группа G, заданная системой образующих а„ iel, и системой соотношений a, а, a, ... = а, а, а, ..., /, j e l, где слова, стоящие слева и справа, состоят каждое из ти чередующихся букв д„ а/, при этом тч элементы некоторой матрицы Кокстера (т/у),^с/, соответствующей группе G [2]. Обозна­ чая символом <ab>n слово aba..., включающее т чередующихся букв а, Ь, за­ пишем представление группы Артина в виде: G = к aiaJ = ам: i , j e l (1) Определенные таким способом группы являются естественным обобще­ нием групп кос, введенных Артином. Группа Артина называется группой Артина конечного типа, если соот­ ветствующая ей группа Кокстера G =(k L , '( a'ai Y ' ={aja) m>,A J e I <ai V i,y e /} (2) является конечной группой. Данный класс групп был введен Брискорном и Сайто [4], в работе полностью описаны ими и решены проблемы равенства и сопряженности слов. Группа кос, в частности, является группой Артина конеч­ ного типа. Полугруппа G ' = ( ( k L ; (a,aj)m“ = («/«<Р .«- J ^ 1)) (3) соответствующая группе G называется полугруппой (моноидом) Артина. Если G группа Артина конечного типа, то С* вложима в G [4]. Группа Артина G называется группой Артина большого типа, если V i, )е /и з того, что i*j\ m,j> 3. 1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, грант Jfe 004)1-00767. 139