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

Шатрова Н.П.' Тула) ОЦЕНКА СТЕПЕНИ СЛОЖНОСТИ АЛГОРИТМА РЕШЕНИЯ ПРОБЛЕМЫ ТОЖДЕСТВА СЛОВ И СОПРЯЖЕННОСТИ ДЛЯ ОДНОГО КЛАССА ГРУПП В этой работе дана оценка степени сложности алгоритма решения проблемы тождества слов и сопряженности в классе ко­ нечно определенных групп. Множество определяющих слов каждой группы симметризсвано и имеет меру налегания ■< j- . Обозначим рассматриваемый класс групп через . Группа G = < a 1, . . . , « л . ; * , , ' > принадлежит классу к < Ь если выполнены условия: 1) множество определяющих слов { R-L } замкнуто относите­ льно взятия обрг ’ного элемента и взятия циклических перестано­ вок букв определяющего слова; 2 ) если определяющие слова R i и невзаимнообратны.то при сокращении произведения /? R . поглощается < 4 букв слова R- . ^ Условие I ) определяет понятие симметризованного множест­ ва. Решение проблемы тождества слоэ для этого кг оса групп принадлежит Линдону OiJ , решение проблемы сопряженности слов Муллу Г 21. Оценка степени сложности алгоритма решения проблемы тож­ дества слов дая конечно порожденных групп изоморфных группе матриц над полем подучена Липтоном и оалкштойном [3 1 . Алго­ ритм решения проблемы тождества слов для этих групп вычисляет­ ся с логарифмической емкостью. Ряд интересных р езу л ь т а т о в ,о т - носящкх'-я к вычислению оценки степени сложности алгоритма,со­ держится в работе Еолиева М.К. [ 4 ] . В данной работе сложность алгоритма решения проблемы тождества слов и сопряженности описана в терминах сигнализи­ рующей функции времени. Верхняя оценка сигнализирующей функ­ ции времени получена путем построения конкретной машины Тьк>- ринга (МТ) для реализации названных алгоритмов. Нижняя оценка сигнализирующей функции времени пслучзна диагональным методом, примененным к рекурсивной последовательности трут из класса К ( $ ) . § I . Определения, понятия, основные р е зу л ь та та " Все определения и понятия, связанные с вопросом оцегош сложности алгоритма, можно найти в £51. Введем определения - 3 -