Алгоритмические проблемы и тождества в полугруппах со свойством Черча-Россера тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

РГБ ОД

г 2 вив

На правах рукописи

ТРУШЩЫИ Юрмн Эдвардовнч

АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ II ТОЖДЕСТВА В ПОЛУГРУППАХ СО СВОЙСТВОМ ЧЕРЧА-РОССЕРА

Специальность 01.01.06 — Математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1995

Работа выполнена в Московском педагогическом государственном университете им. В. И. Ленина на кафедре алгебры.

доктор физико-математических наук, профессор ПЧЕЛИНЦЕВ С. В.

Официальные оппоненты:

доктор физико-математических наук, профессор ГЛУХОВ М. М.,

кандидат физико-математических наук, доцент МИХАЛЕВ А. А.

Ведущая организация — Ивановский государственный упп-

Б аудитории 301 на аассдашш диссертационного долита К. 053.01.02 и Московском педагогическом государственном университете им. В. И. Ленина по адресу: 107140, Москва, Крапгапруцная, 14, МПГУ им. В. И. Ленина.

С диссертацией можно ознакомиться в библиотеке МПГУ: 1110435, Москва, Малая Пироговская, 1, МПГУ им. В. И. Ленина.

Научный руководитель:

верситет.

Защита состоится

Автореферат разослан

Уче 'о Совета

ЕВ Г. А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Б = < ; А^В,,..., А.^ ,...>. (1)

Назовем определяющие слова А1Д2,...,А^,... старшими, слова В1 ,В2,..... - младшими. Под элементарным преобразованием в полугруппе Б понимается переход от слова вида РА^Ц к слову И^а или обратно, где Р,<3 - произвольные слова из Б, А1=В1 - одно из определяющих соотношений. Элементарные преобразования вида РА10 —► РВ10 назовем сокращениями. Таким образом, сокращение - это элементарное преобразование, заменяющее старшее слово на младшее.

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

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

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

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

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

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

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

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

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

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

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

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

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

- является ли полугруша Б группой?

- имеет ли Б кручение?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались:

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

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

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

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

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

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

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

ОБЗОР СОДЕРЖАНИЯ ДИССЕРТАЦИИ

Во введении даны основные определения, освещены результаты, полученные ранее другими авторами, кратко изложено содержание диссертации.

В главе 1 изучаются моноида, заданные конечными монади-ческими непредставлениями со свойством Черча-Россера. В §1 вводится понятие голугрупповой диаграммы и описываются диаграммы для изучаемых моноидов. В §2 доказываются леммы о преобразовании диаграмм. Грубо говоря, эти леммы утверждают следующее: если имеется диаграмма с некоторыми свойствами, то имеется и диаграмма с теми же свойствами, но достаточно малым количеством граней. В §3 доказывается следующая теорема, отвечающая на Еопрос из [11).

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

В конце параграфа приведены замечания, показывающие, что основную теорему в некотором смысле нельзя обобщить.

Глава 2 посвящена полугруппам, заданным одним определящим соотношением А=В. В §1 получено комбинаторное описание слов А,В в случае, когда копредставлеяие удовлетворяет свойству Черча-Рассера. При этом использованы метода С.И.Адяна-Г.У.Оганесяна 121 и следующая доказанная автором лемма о полугруппах Черча-Россера без левых циклов.

Лемма 4. Пусть полугруша П задана системой определяющих. соотношений А1=В1 (1=1,... ,к) без левых циклов. Пусть также эта система удовлетворяет свойству Черча-Россера (слова А,.....А^. - старшие). Тогда:

1. Если А3 £ Б? , Ак = РЕ , где Б или I? непусто, то .

2. Если А3 г 5АкИ , ТО А^ 3 Ак , 3=к.

В §2 доказываются теоремы о разрешимости проблемы вхождения в циклическую подполугруппу для полугрупп, заданных одним определяющим соотношением (или копредставлением без левых циклов) со свойствами Черча-Россера и нетеровости.

В главе 3 описывается множество решений уравнения ХУ=УХ в специальных моноидах со свойством Черча-Россера. Получено комбинаторное (теорема 2) и алгебраическое (теорема 3) описания. Для формулировки теоремы 3 необходимо ввести понятие сопряженности подаоноидов: подаоноиды Н1 и Н2 моноида М сопряжены между собой, если в М существуют элементы а,Ь такие, что Н^ = аН2 и ЬН? = Н2Ь.

Теорема 3. Пусть ХУ - УХ в специальном моноиде Черча-Россера М. Тогда для подмоноида К = < Х,У > справедливо одно из следующих утверждений:

1. К содержится в бесконечном циклическом подмоноиде моноида М;

2. К является циклической подгруппой моноида М;

3. К содержит нетривиальный идемпотент и сопряжен с подмоноидом С, где С - подмоноид бесконечного циклического моноида ила циклическая подгруппа.

Доказательства этих результатов - технические, связанные с рассмотрением различных возможностей. Б тех случаях, когда удается свести задачу к подгруппам, применяется

теорема Сквайара [171, описывающая подгруппы специальных моноидов Черча-Россера.

В главе 4 на основании результатов главы 3 доказываются теоремы об описании коммутативных подмоноидов. При этом получены некоторые результаты, имеяцае самостоятельное значение. Приведем некоторые из них. В §1 исследуются порядки элементов и циклические подмоноида. Доказаны следующие утверждения.

Лемма 2. Пусть X - произвольный нетривиальный элемент специального моноида Черча-Россера.

(А) X - элемент конечного порядка тогда и только тогда, когда его неприводимая форма имеет вид

X = BOyi, )Ч ,

где t > 0 , АВ=1, и если (И2Т11* 1, то существует определяющее слово (t^Ug)8 при в Я.

(Б) X - элемент бесконечного порядка тогда и только тогда, когда его неприводимая форма имеет вид

X з BGA ,

где АВ=1, С 1, слово ВСША неприводимо при любом т>0.

Леша 6. В специальном моноиде Черча-Россэра не существует бесконечной строго возраставдей цепочки (А) циклических подмоноидов; (Б) циклических подгрупп.

Следствие 5. В специальном моноиде Черча-Россера выполнено свойство: если два максимальных циклических подмоноида имеют общий элемент, не являющийся идемпотентом, то эти подмоноида совпадают.

Второй параграф посвящен централизаторам элементов.

Теорема 1. Пусть g - произвольный элемент конечно порок-денного специального моноида М со свойством Черча-Россера. Централизатор 0(g) этого элемента конечно порожден.

Отмечается, что если моноид М конечно определен, то существует алгоритм, строящий множество поровдающих для C(g).

Теорема 2. Пусть Х™ не является идемпотентом. Тогда в специальном моноиде Черча-Россера централизатор элемента X

совпадает с централизатором элемента X®.

В третьем параграфе главы 4 изучаются идемпотентн специальных моноидов Черча-Россера.

Лемма 10. Если идемпотентн R,S специального моноида Черча-Россера коммутируют, то их произведение равно одному из сомножителей.

' В лемме 12 приводится описание идемпотентов, уточняющее аналогичное описание, полученное ранее Ф.Отто. Также доказана

лемма 13. Если X не идемпотент, то X коммутирует лишь с конечным числом идемпотентов.

Последний параграф посвящен доказательству следующих теорем.

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

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

Теорема 5. Конечный коммутативный подооноид идемпотентов в специальном моноиде Черча-Россера сопряжен с тривиальным подмоноидом. Бесконечный коммутативный подмоноид идемпотентов в специальном моноиде Черча-Россера изоморфен подмо-ноиду идемпотентов бициклического моноида В=< а,Ъ ; аЪ=1 >.

ЛИТЕРАТУРА

1. Адян С.И. Определящие соотношения и алгоритмические проблемы для групп и полугрупп // Труды Мат. ин-та АН СССР. 1966. Т.85. С.1-124.

2. Адян С.И., Оганесян Г.У. К проблемам равенства и делимости в полугруппах с одним определяющим соотношением // Известия АН СССР. Сер. матем. 1978. Т.42. J62. С.219-225.

3. Гриндлингер Е.И., Гриндлингер М.Д. Алгоритм для решения проблемы тождества слов для некоторых полугрупп //

Изв. ВУЗов. Математика. 1970. Ю. С.45-47.

4. Кашинцев Е.В. К проблеме равенства слов для специальных полугрупп // Известия АН СССР. Сер. матем. 1978.

Т.42. №6. С.1401-1416.

5. Классен В.П. Строение подгрупп с тождеством в группах с малой мерой налегания определяющих слов // Матем. заметки. 1978. Т.24. J63. С.305-313.

6. Мучник А.А., Семенов А.Л. Послесловие // В кн.: Саломаа А. Жемчужины теории формальных языков. М.: Мир, 1986. С.145-152.

?. Шеврин Л.Н., Волков М.В. Тождества полугрупп // Изв. ВУЗов. Математика. 1985. 1. С.3-47.

8. Шнеерсон Л.М. Конечно-определенные полугруппы с нетривиальными тождествами // Сиб. матем. жур. 1982. Т.23. #1. С.160-171.

9. Avenhaus J., Book R.V., Squier С.С. On expressing commutativlty by finite Church-Rosser presentations // Inform. Theor. 1984. V.18. № . P.47-52.

10. Book R.V. Decldable sentences of Church-Rosser congruences // Theor. Сотр. Science. 1983. V.24...P.301-312.

11. Book R.V. Thue systems as rewriting systems // J. Symb. Comput. 1987. 7.3. №1. P.39-68.

12. Church A., Rosser B. Some properties of conversion // Trans. Amer. Math. Soc. 1536. V.39. P.472-482.

13. Madlener K., Otto P. About the descriptive power of certain classes of finite string-rewriting systems // Theor. Сотр. Science. 1989. V.67. Ji£-3. P. 143-172.

14. Madlener K., Otto P. Commutativlty in groups presented by finite Church-Rosser Thue systems // Inform. Theor. 1988. V.22. №1. P.93-111.

15. Nlvat M. Congruences parfaites et quasi-parfaites // Semlnaire Dubreull, 1971-72. T.7.

16. Otto P., Wrathall C. A note on Thue systems with a single defining relation // Math. Syst. Theory. 1985. V.18. Я£. P.135-143.

17. Squier C.C. Units of special Church-Rosser monoids // Theor. Сотр. Science. 1987. V.49. № . P.13-22.

- и -

Публикации автора по теме диссертации

18. Трубицын Ю.Э. Свободные подмоноида в моноидах Черча-Россера // Меадунар. конф. по алгебре: Тезисы докл. по логике и универсальным алгебрам, прикладной алгебре. Новосибирск, 1991. С.146.

19. Трубицын Ю.Э. Алгоритмические проблемы для . монадических систем с условием Черча-Россера // Деп. в ВИНИТИ, Л2396-В92. М., 1992. С.1-25.

20. Трубицын Ю.Э. Коммутативность в специальных моновдах Черча-Россера // Одиннадцатая меадэесп. конф. по матем. логике: Тезисы докладов. Казань, 1992. С.142.

21. Трубицын Ю.Э. Алгоритмические проблемы для подооноидов некоторых специальных моновдов // Одиннадцатая меяфесп. конф. по матем. логике: Тезисы докладов. Казань, 1952. С.141.

22. Трубицын Ю.Э. Коммутативность в специальных полугруппах со свойством Черча-Россера // Алгоритмические проблемы теории групп и полугрупп. Тула, 1994. С.104-132.