УДК 512.54:004.021
DOI: 10.36871/2618-9976.2021.02.001

Авторы

Добрынина Ирина Васильевна
Доктор физико-математических наук, доцент, профессор кафедры высшей математики, Академия гражданской защиты МЧС России, Химки, Россия
Туренова Елена Львовна
Кандидат физико-математических наук, доцент, доцент кафедры высшей математики, Академия гражданской защиты МЧС России, Химки, Россия

Аннотация

Основными алгоритмическими проблемами комбинаторной теории групп, поставленными М. Деном и Г. Титце в начале XX в., являются проблемы равенства, сопряженности слов и изоморфизма групп. Однако данные проблемы, как следует из результатов П.С. Новикова и С.И. Адяна, оказались неразрешимы в классе конечно определенных групп. Поэтому алгоритмические проблемы стали рассматриваться в различных классах групп.
Проблема сопряженности слов допускает два обобщения. С одной стороны, рассматривается проблема сопряженности подгрупп, т.е. проблема построения алгоритма, позволяющего для любых двух конечно порожденных подгрупп некоторой группы установить, сопряжены они в этой группе или нет. С другой стороны, ставится проблема обобщенной сопряженности слов, т.е. проблема построения алгоритма, позволяющего для любых двух конечных множеств слов некоторой группы определить, сопряжены они в этой группе или нет. Объединяя в одно оба эти обобщения, получаем проблему обобщенной сопряженности подгрупп.
Группы Кокстера введены в 30е годы прошлого века, в них алгоритмически разрешимы проблемы равенства и сопряженности слов. Для решения других алгоритмических проблем выделяются различные подклассы. Отчасти это связано с неразрешимостью в группах Кокстера еще одной важной проблемы – проблемы вхождения, т.е. проблемы существования алгоритма, позволяющего для любого слова и произвольной конечно порожденной подгруппы некоторой группы определить, принадлежит ли это слово данной подгруппе или нет. В статье доказывается алгоритмическая разрешимость проблемы обобщенной сопряженности подгрупп в группах Кокстера с древесной структурой.

Ключевые слова

алгоритмическая проблема
алгоритм
группа Кокстера
древесная структура
сопряженность
подгруппа