Алгоритмические проблемы и тождества в полугруппах со свойством Черча-Россера Трубицын, Юрий Эдвардович

Введение к работе

Актуальность темы. Диссертация посвящена исследованию некоторых классов полугрупп, заданных своим копредставле-нием, т.е. с помощью порождающих элементов и опре делящих соотношений. Дадим определение рассматриваемых полугрупп. Пусть полугруппа S имеет копредставление

S = < a_va_z,...,a_lt... ; А₁ =В₁,..., А^В^ ,...>. (1)

Назовем определяющие слова А₁Д_г,...,А ,... старшими, слова В., ,В₂,...,В.,... -младшими. Под элементарным преобразованием в полугруппе S понимается переход от слова вида PA^Q к слову PBjQ или обратно, где P,Q - произвольные слова из S, А₁=В₁ - одно из определяющих соотношений. Элементарные преобразования вида PA^Q — PBjQ назовем сокращениями. Таким образом, сокращение - это элементарное преобразование, заменяющее старшее слово на младшее.

Копредставление (1) по определению удовлетворяет свойству Черча-Россера, если для любой пары слов Х,У выполнено условие; X = Y в полугруппе S тогда и только тогда, когда существует слово Z, которое может быть получено из X и из Y при помощи сокращений. Таким образом, произвольную последовательность элементарных преобразований, переводящую слово X в слово Y, можно заменить последовательностью определенного (и довольно простого) вида. Иногда, допуская вольность речи, говорят, что свойству Черча-Россера удовлетворяет сама полугруппа, имея в виду ее фиксированное копредставление (в каждом определяющем соотношении которого выделено старшее слово).

Однако одного свойства Черча-Россера недостаточно для получения каких-либо нетривиальных результатов, поскольку любая счетная полугруппа может быть задана копредставлением с этим свойством. Поэтому необходимо наложить еще какие-то условия на класс рассматриваемых полугрупп. Введем следующее важное определение.

Копредставление (1) называется нетеровым, если для произвольного слова V любая последовательность сокращений, начинающаяся с V, обрывается через конечное число шагов.

Из определений сразу следует, что если полугруппа задана конечным копредставлением со свойствами Черча-Россера и нетеровости, то существует простой алгоритм для нахождения канонической формы элементов этой полугруппы. Этот алгоритм заключается в вшолнении всевозможных сокращений до получения несократимого слова. Свойство нетеровости гарантирует, что процесс сокращений не может быть бесконечным, а из свойства Черча-Россера следует, что порядок сокращений не играет роли. Разумеется, для конечных копредставлений со свойствами Черча-Россера и нетеровости разрешима проблема равенства слов.

Важность изучения таких копредставлений (не обязательно в рамках теории полугрупп) отмечается, например, в [6, с.147-148]. Заметим, что вышесказанное позволяет считать такие полугруппы одним из возможных полугрупповых аналогов активно исследуемых сейчас гиперболических групп.

Свойство Черча-Россера в той или иной форме неоднократно использовалось при изучении проблемы равенства для полугрупп и групп, для доказательства разрешимости элементарных теорий различных алгебр, в теории формальных языков и т.д. Само название этого свойства связано с одной теоремой комбинаторной логики [12]. Однако как предмет самостоятельного изучения это свойство появляется, к сожалению, только в работах зарубежных математиков (см. обзоры [11,13] и обширную библиографию к ним). В качестве исключения можно назвать малоизвестную заметку [3], где фактически было не только определено свойство Черча-Россера, но и содержались важные идеи, впоследствии появившиеся в других работах.

Обычно начало систематического изучения свойства Черча-Россера связывают с именем М.Нива [15] и его коллег, работавших на стыке теории формальных языков и алгебры в начале 70-х годов. За четверть века интенсивных исследований было получено немало результатов о полугруппах со свойством Черча-Россера. Хорошие обзоры состояния дел в этой области

даны в [11] и [131, причем в первой из этих статей упор делается на алгоритмические вопросы, во второй - на алгебраические.

Опишем кратко результаты, кмеодив непосредственное отношение к проблемам, затронутым в диссертации. Сначала введем некоторые обозначения. Символы = , = , 1 , |Х| означают, соответственно, равенство элементов полугруппы, графическое равенство, пустое слово, длину слова X.

Копредставлеше (1) назовем специальным (а полугруппу S

- специальной полугруппой ИЗ), если для любого і B_t = 1.
Нопредставление (1) назовем монадическим, если для любого і
|А_±| > IBJ < 1. Отметим, что таблица умножения любой полу
группы представляет собой монадическую систему определяющих
соотношений со свойствами Чзрча-Россера и нетеровости.

Для конечно определенных монадических полугрупп со свойством Черча-Россера известна разрешимость многих алгоритмических проблем. Кроме уже упоминавшейся проблемы равенства, для них разрешима проблема конечности. Ф.Отто установил разрешимость следувдих алгоритмических проблем:

является ли полугруппа S свободной?

является ли полугруппа S группой?

имеет ли S кручение?

В статье МО] Р.Бук предложил основанный на теории регулярных языков подход к решению алгоритмических проблем в монадических полугруппах со свойством Черча-Россера. В 1101 была доказана разрешимость целого класса алгоритмических проблем. Однако, как отмечается в [11], многие проблемы не поддаются решению таким способом. В качестве открытого вопроса в [11, с.59] отмечен следующий: существует ли алгоритм, который по конечному множеству слов в монадической полугруппе со свойством Черча-Россера выясняет, свободен ли подаоноид, порожденный этим множеством. Основным результатом первой, главы диссертации является положительный ответ на вопрос Р.Бука, причем предложенный способ применим и к многим другим алгоритмическим проблемам в полугруппах рассматриваемого класса. Этот способ основан на рассмотрении полугрушовых диаграмм [4].

- є -

Вторая глава диссертации посвящена изучению полугрупп, заданных одним определяющим соотношением со свойством Черча-Россера. Учитывая, что свойство Черча-Россера в сочетании с нетеровостью влечет разрешимость проблемы равенства, и что эта проблема для произвольных полугрупп с одним соотношением остается нерешенной, естественно поставить следующие задачи:

1. Описать все копредставления с одним соотношением А=В, обладающие свойством Черча-Россера [161;

2. Найти алгоритм, который для любого копредставления с одним соотношением А=В выяснял бы, будет ли оно нетеровым (известный вопрос).

Вторая задача, насколько известно автору, не решена и является, по-видимому, довольно сложной. Что касается первой задачи, описание слов А и В было начато в статье [161. Завершить его удается с использованием методов работы С.й.Адяна и Г.У.Оганесяна 121. Это описание и является основным результатом второй главы диссертации. Тем самым получен ответ на вопрос, поставленный в [16, с.142]. Кроме того, изложенный способ применим к решению некоторых других задач для полугрупп Черча-Россера с одним соотношением, что иллюстрируется теоремой о разрешимости проблемы вхоздения в циклическую подполугруппу.

Обратимся к результатам, связанным с главами 3,4 диссертации. Представляют большой интерес вопросы о том, какие полугруппы (и группы) могут быть заданы нетеровым копред-ставлением со свойством Черча-Россера, какие подполугруппы содержатся в них. и т.д. Например, если ограничиться конечными монадическими копредставлениями, то мы получим класс, содержащий все конечные полугруппы, конечно порожденные свободные полугруппы, свободные произведения конечного числа циклических групп ж многие другие полугруппы (в частности, хорошо известный бивдклический моноид < а,Ъ ; ао=1 >). В общем случав поставленные вопросы довольно сложны. Исследованию^- поддаются лишь некоторые частные случаи, причем, как отмечено в 113, с.1451, почти все полученные результаты относятся к группам. Например, К.Ыадленер и Ф.Отто в [141 описали конечно порожденные абелевы подгруппы групп, имеющих

конечное копредставление Черча-Россера. Что касается полугрупп, не являющихся группами, о них известно очень мало. Можно упомянуть работы [1,9,17], где получены различные результаты в указанном направлении. Например, в [17] были описаны подгруппы специальных моноидов со свойством Черча-Россера, в [9] изучались коммутативные моноиды с сокращением. Однако в настоящее время не может быть и речи о какой-либо теории, близкой к завершению, в области алгебраического описания конкретных классов полугрупп со свойством Черча-Россера. Для формирования такой теории имеющихся результатов и методов недостаточно.

В главах 3,4 диссертации исследуется свойство коммутативности в моноидах, имеющих специальное (не обязательно конечное) копредставление со свойством Черча-Россера. В отличие от [11, мы имеем дело с подмоноидами. В связи с этим заметим, что хотя тождествам полугрупп посвящена обширная литература (например, [1,7,8]), по-видимому, почти ничего не известно о строении подполугрупп с тождеством 3 тех или иных полугруппах, не являющихся группами. Для групп вопрос во многих случаях прояснен. Типичный результат [51: если подгруппа группы с малым сокращением удовлетворяет нетривиальному тождеству, то она либо циклическая, либо является свободным произведением двух групп второго порядка.Представляется естественным попытаться перенести результаты о подгруппах с тождеством на подполугруппы с тождеством. Разумеется, прямое перенесение невозможно. В частности, как выяснилось, вопрос усложняется из-за наличия в исследуемых подмоноидах нетривиальных идемпотентов. Однако оказалось, что от вдемпотентов можно избавиться, переходя к сопряженным годмоноидам, которые уже имеют простое строение. Таким образом, можно сделать вывод, что в изучаемых полугруппах "групповые" свойства могут выполняться лишь с точностью до сопряженности. Полученные результаты подсказывают путь, по которому может идти исследование коммутативных подмоноидов в некоторых других классах моноидов, например, в классе из Ш.

Итак, по мнению автора, описание коммутативных подмоно-

идов, полученное в диссертации, может быть интересным не только в рамках теории полугрупп со свойством Черча-Россера, . но и как один из немногих известных примеров описания подполугрупп с теми или иными свойствами в каких-либо интересных полугрушах, заданных копредставлением.

Методы исследования. В работе применяются комбинаторные методы, связанные с рассмотрением различных возможностей. В главе 1 существенно используется метод полугрупповых диаграмм.

Цели диссертационного исследования.

3. Разработка метода, позволяющего исследовать разрешимость алгоритмических проблем для полугрупп, заданных монадическим копредставлэнием со свойством Черча-Россера;

4. Комбинаторное описание копредставлений с одним определяющим соотношением, задающих полугруппу со свойством Черча-Россэра;

5. Описание решений уравнения XY=YX в специальных полугруппах со свойством Черча-Россера;

6. Изучение коммутативных подмоноидов в специальных полугруппах со свойством Черча-Россера.'

Новизна результатов. Основные результаты диссертации являются новыми. Важнейшие из них:

7. Теорема об алгоритмической разрешимости проблемы свободы конечно порожденного подмоноида в монадических полугруппах со свойством Черча-Россера;

8. Комбинаторное описание копредставлений с одним определяющим соотношением, удовлетворяющих свойству Черча-Россера;

9. Описание коммутативных подмоноидов в специальных моноидах со свойством Черча-Россера.

Теоретическое и практическое значение. Работа имеет теоретический характер, ее результаты могут найти применение при исследовании различных вопросов теории полугрупп.

Апробация работы. Результаты диссертации докладывались: 1. На Международной конференции по алгебре, посвященной 70-летию А.И.Ширшова (Барнаул, 1991 г.);

2. На алгебраическом семинаре под руководством Д.И.Молда-ванского (Ивановский университет, 1991 г.);

3. На 11-й межреспубликанской конференции по математической логике (Казань, 1992 г.);

4. На алгебраическом семинаре под руководством А.А.Фомина (Московский педагогический университет, 1995 г.);

5. На алгебраическом семинаре под руководством В.Н.Без-верхнего (Тульский педагогический университет, 1991-1995 г.)

Публикации. Основное содержание диссертации отражено в пяти публикациях. Их список приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, списка литературы и изложена на 121 странице. Список литературы содержит 120 наименований.