Функция роста некоторых двупорожденных полугрупп тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

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

Кудрявцева Лика Александровна

ФУНКЦИЯ РОСТА НЕКОТОРЫХ ДВУПОРОЖДЕННЫХ ПОЛУГРУПП

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

Автореферат

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

2 4 май 2012

Ульяновск — 2012 г.

005044896

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

Работа выполнена на кафедре Высшей математики № 1 в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Национальный исследовательский университет «МИЭТ»

Научный руководитель: доктор физико-математических наук,

профессор

Кожухов Игорь Борисович доктор физико-математических наук, профессор механико-математического факультета Московского государственного университета имени М. В. Ломоносова Зайцев Михаил Владимирович доктор физико-математических наук, профессор кафедры математики Финансового университета при Правительстве Российской Федерации Тищенко Александр Владимирович ФГВОУ ВПО «Московский педагогический государственный университет»

Защита диссертации состоится «13» июня 2012 г. в 1300 часов на заседании диссертационного совета Д 212.278.02 при ФГВОУ ВПО «Ульяновский государственный университет» по адресу: ул. Набережная р. Свияги, 106, корп. 1, ауд. 703.

С диссертацией можно ознакомиться в библиотеке Ульяновского государственного университета. С авторефератом можно ознакомиться на сайте ВУЗа http://www.uni.ulsu.ru и на сайте Высшей аттестационной комиссии при Министерстве образования и науки РФ http://www.vak.ed.gov.ru.

Отзывы по данной работе просим направлять по адресу: 432017, г. Ульяновск, ул. Л.Толстого, д. 42, УлГУ, Отдел послевузовского профессионального образования.

Автореферат разослан «12» мая 2012 г. Ученый секретарь

диссертационного совета М.А.Волков

Ведущая организация:

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

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

Если полугруппа А задана множеством порождающих элементов М и множеством определяющих соотношений Е , то проблема равенства слов для полугруппы А состоит в описании алгоритма, который определяет, представляют ли два слова w\% wi 6 М* один и тот же элемент полугруппы А. (Здесь М* - свободная полугруппа над алфавитом М). Если такой алгоритм существует, то проблема равенства слов называется разрешимой; если доказано, что такого алгоритма нет, то алгоритмическую проблему называют неразрешимой. A.A. Марков1 и Э. Л. Пост2 в 1947 году независимо установили алгоритмическую неразрешимость проблемы равенства слов для некоторых конечно определённых полугрупп. Основные сведения из теории полугрупп можно найти в книгах Е. С. Ляпина3, А. Клиффорда и Г. Престона4.

При работе с образующими элементами и определяющими соотношениями часто возникают чисто комбинаторные вопросы. Эти вопросы связывают алгебру с комбинаторикой и дискретной математикой. Комбинаторным проблемам, связанным со словами, посвящена монография А. М. Шура5, а также большое количество работ, например: работа Г. Лаллемана6 о проблеме равенства слов, работы Р. Бука7 и С. Рэтхолл8 о полугруппах, заданных одним определяющим соотношением, работа Ю. Матиясевича9 о полугруппах, за-

'Марков А. А., ДАН СССР, 1947, т.55, №7, с. 587-90.

2Post Е. L., J. Symbol. Logic, 1947, v.12, №1, p. 1-11.

гЛятт Б. С. Полугруппы. М.: Гос. изд-во физ.-мат. лит., 1960.

4Клпффорд А., Престон Г. Алгебраическая теория полугрупп, тт. 1, 2. М.: Мир, 1972.

5 Шур А. М. Комбинаторика слов: учеб. пособие.- Екатеринбург: Изд-во Урал, ун-та, 2003.

6LaI!ement G. The word problem for Thue rewriting systems // Lecture Notes in Computer Science, 1995, v.909, p. 27-38.

'Boot R. V. A note on special Thue systems with a single defining relation 11 Math. Systems Theory, 1983, v.16, p. 57-60.

sWrathaIl C. Confluence of one-rule Thue systems // Lecture Notes in Computer Science, 1992, v.572, p. 237-246.

9Mztiyasevich Y. Word Problem for Thue Systems with a Few Relations // Lecture Notes

данных несколькими определяющими соотношениями.

Диссертационная работа посвящена изучению полугрупп, заданных множеством порождающих элементов М = {a, b} из двух элементов а и Ь, и одним или несколькими определяющими соотношениями, представляющими собой равенство двух слов одинаковой длины.

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

Функцией роста конечно пороледенной полутруппы А относительно множества порождающих элементов М, \М\ < со, мы будем называть функцию /м : N N, сопоставляющую числу п 6 N число всех различных элементов полугруппы Л, записываемых словами длины п в алфавите М. Это немного отличается от определений, приведенных в статье Л. Н. Шеврина10, §2, или в монографии В. А. У фнаровского11.

Объектом исследования в работе являются полугруппы, заданные одним или несколькими равенствами слов длины два или три над двухбуквенным алфавитом. Нахождение функций роста таких полугрупп, мощности и строения классов эквивалентности является предметом исследования. Цель и задачи работьг. Основной целью диссертационной работы является исследование полугрупп над двухбуквенным алфавитом, порожденных одним или несколькими соотношениями слов длины два и три. Для достижения цели были поставлены и решены следующие задачи:

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

2. Установлен общий вид слов в классах эквивалентности конгруэнций, порожденных одним или несколькими соотношениями слов длины два и три.

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

in Computer Science, 1995, v.909, p. 39-53.

'"Шевршг Л. H. Полугруппы. В сб. Общая алгебра, т. 2, гл. IV, сер. СМБ, - М.: Наука, 1991, с. 11 - 191.

11 Уфнаровский В. А. Комбинаторные и асимптотические методы в алгебре, Алгебра -6, Итоги науки и техн. Сер. Соврем, пробл. мат. Фундам. направления, 57, ВИНИТИ, М., 1990, с. 5 - 177.

теории графов, теории переписывающих систем или TRS (Term Rewriting System), а также некоторые методы перечислительной комбинаторики. Научная новизна. В диссертационной работе получен ряд результатов о строении полугрупп, заданных одним определяющим соотношением длины два, одним определяющим соотношением длины три, а также несколькими определяющими соотношениями длины два и три. Полученные результаты являются новыми.

Научные положения, выносимые на защиту.

1. Для свободной двупорожденной полугруппы описаны конгруэнции, порожденные всевозможными парами слов длины два, длины три, а также совокупностями пар слов длины два и три.

2. Вычислены функции роста полугрупп, порожденных двумя элементами, с соотношениями, описанными в п. 1.

3. Установлен общий вид слов в классах эквивалентности вышеназванных конгруэнций свободных двупорожденных полугрупп и вычислены мощности классов в ряде случаев.

Достоверность результатов проведенных исследований. Достоверность результатов, полученных в данной работе, определяется обоснованными теоретическими выкладками и строгими доказательствами, опирающимися на методы алгебраической теории полугрупп и комбинаторные методы. Практическая и теоретическая ценность. Работа носит теоретический характер. Полученные результаты могут найти применение в исследованиях теории полугрупп и в задачах компьютерной алгебры. Апробация работы. Основные результаты и вопросы диссертации обсуждались в виде выступлений на следующих конференциях и семинарах:

- Четырнадцатая всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика». Москва. 18 - 20 апреля 2007 г.;

- Международная научная конференция «Современные проблемы дифференциальной геометрии и общей алгебры», посвященная 100-летию со дня рождения профессора В. В. Вагнера. Саратов. 5-7 ноября 2008 г.;

- Российская школа-конференция с международным участием «Математика, информатика, их приложения и роль в образовании». Москва. 14 - 18 декабря 2009 г.;

- Семнадцатая международная конференция студентов, аспирантов и молодых ученых «Ломоносов». Москва. 12 - 15 апреля 2010 г.;

- Седьмая международная конференция <Алгебра и теория чисел: современные проблемы и приложения», посвященная памяти профессора А. А. Карацубы. Тула. 11 - 16 мая 2010 г.;

- Семинары «Кольца и модули» кафедры Высшей алгебры Московского государственного университета.

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

Публикации. По теме диссертации опубликовано 10 работ, в том числе две статьи в журналах из списка ВАК.

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

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертации. Приводится аннотация работы.

В первой главе изложены предварительные сведения, основные определения и результаты теории переписывающих систем (Term Rewriting Systems). Теория переписывающих систем является удобным инструментом для нахождения функция роста групп и полугрупп. Например, в работе Р. И. Григор-чука12 получена формула для выражения числа допустимых слов, т. е. слов, не содержащих вхождения запрещенных подслов. Эта формула может быть применена для вычисления функций роста групп и полугрупп, см., например, работу М. Д. Мамагани13. В работе М. Д. Мамагани14 была построена полная конечная система переписывающих правил для групп Коксетера.

Во второй главе полностью разобрайы полугруппы, заданные одним определяющим соотношением, представляющим собой равенство слов длины

12Грнгорчук Р. И. Функции роста, переписывающие системы и эйлерова характеристика // Матем. заметки, 58:5 (1995), с. 653-668.

13Мамагатг М. Д. О функциях роста групп поверхностей // Матем. заметки, 58:5 (1995), с. 681-693.

"Мамагани М. Д. Переписывающие системы и полвыП ряд роста для треугольпых групп Коксетера // Матем. заметки, 71:3 (2002), с. 431-439.

два. Всего двухбуквенных соотношений существует 6. С точностью до инверсии и перемены букв а и Ь местами, принципиально разными будут лишь следующие 3 соотношения:

аа - аЬ, аЬ = Ьа, аа = ЬЬ.

Каноническим словом в данном классе будем называть слово, наименьшее относительно лексикографического порядка. Если ги € М", то через К(ш) обозначим класс эквивалентности, в котором лежит слово ги. Пусть |ЛГ(гу) | -число элементов в классе эквивалентности К(ги). Число элементов в классе эквивалентности будем также называть мощностью этого класса.

Предложение 2.1. Функция роста полугруппы А, заданной множеством образующих элементов М = {а, Ь} и одним определяющим соотношением аа = аб, равна п + 1. Канонические слова в каждом классе имеют вид

= Ь'а"-', г = 0,1, ...,п. Число элементов в каждом классе равно |Л"(ги()| = 1=0,1,...,п-1и |ЛТК)| = 1.

Предложение 2.2. Функция роста полугруппы А, заданной множеством образующих элементов М = {а, 6} и одним определяющим соотношением аЪ = Ьа, равна п + 1. Канонические слова в каждом классе имеют вид го,- = ап~'Ь\ г = 0,1,...,гг. Число элементов в каждом классе равно = С'п,

г = 0,1,...,п.

Предложение 2.3. Функция роста полугруппы А, заданной множеством образующих элементов М = {а, 6} и одним определяющим соотношением аа = ЬЬ, равна п + 1. Канонические слова в каждом классе имеют вид

ги; = а' ■ и, г = 0,1,..., п,

где и - либо пустое слово, либо слово, состоящее из одной буквы 6, либо слово, состоящее из чередующихся букв Ь и а, начиная с Ь.

Сложнее оказалось получить формулу для числа элементов в каждом классе эквивалентности, порожденном соотношением аа = ЬЬ. Во второй главе приведено два доказательства следующей теоремы: первое основано на индукции по тг, второе использует комбинаторную формулу Вандермонда.

Теорема 2.1. Обозначим через а(тг,к) число слов в классе эквивалентности слов длины п, содержащих слово и^ = ак ■ и, 0 < к < п, где и - либо пустое слово (при к -- п), либо состоящее из одной буквы Ь (при к = п - 1),

либо состоящее из чередующихся букв Ь и а, начиная с Ь. Тогда

с!?1.

В заключительной части главы 2 показано, что количество классов эквивалентности слов длины п над двухбуквенным алфавитом в случаях действия соотношений аа = ab и ab = ba может быть найдено как число слов длины п, не содержащих подслова ab. Для соотношения аа = 66 показано, что количество классов эквивалентности слов длины п над двухбуквенным алфавитом может быть найдено как число слов длины п, не содержащих подслов ЬЬ и baa одновременно. Подсчет количества слов длины п, не содержащих одного определенного подслова, уже производился некоторыми авторами. Подобные расчеты сделаны, например, в работах Р. Дорословацки15 и Р. Дорословацки, О. Марковича16 для подслов длины три. Для подсчета количества слов, не содержащих одновременно двух или нескольких подслов, был использован метод трансфер-матрицы (см. Р. Стенли17, С. Хейбач и Т. Мансур18). Подсчет количества слов длины п, не содержащих подслов ЬЬ и baa одновременно, сделан в конце второй главы.

В третьей главе разобраны полугруппы, заданные одним определяющим соотношением, представляющим собой равенство слов длины три. С точностью до инверсии слова и перемены букв о и 6 местами, достаточно рассмотреть лишь 11 соотношений, представляющих собой равенство двух трехбуквенных слов: aab = ааа, aab = aba, aab = abb, aab = baa, aab = bab, aab = bba, aba = ааа, abb — ааа, bab — ааа, bab — aba, bbb = ааа. Показано, что функция роста полугруппы, заданной множеством порождающих элементов М — {а, Ь} и одним из соотношений aab = ааа, aab = aba, aab = abb, aab = baa, aab — bab, aab = bba, abb = ааа, удовлетворяет рекуррентному соотношению a(n) = oc{n — 1) 4- ct(n — 2) 4-1; функция роста полугруппы, заданной множеством порождающих элементов М — {а, 6} и соотношением aba = ааа, удовлетворяет рекуррентному соотношению ß(n) = 2ß(n—l)—ß(n—2)+ß(n—3). Также доказаны следующие теоремы:

15Doroslovacki R. The set of all the words of length n over alphabet {0,1} with any forbidden subword of length three // Novi Sad J. Math, 1995, v.25, X»2, p. 111-115.

'6Doros!avacki R., Markovic O. N-words over any alphabet with forbidden any 3-subwords // Novi Sad J. Math, 2000, v.30, №2, p. 159-163.

17Стенли P. Перечислительная комбинаторика, т.1. M.: Мир, 1990.

18Heubacb S., Mansour Т. Combinatorics of compositions and words. Discrete mathematics and its applications. CRC Press. 2009.

Теорема 3.1. Функция роста полугруппы А, заданной множеством порождающих элементов М = {а,Ь} и одним определяющим соотношением bbb = ааа, равна F„+2 — 1, где F„ - п-ое число Фибоначчи.

Теорема 3.2. Функция роста полугруппы А, заданной множеством порождающих элементов М = {а, Ь} и одним определяющим соотношением bab = ааа, равна Fn+i — 1.

Теорема 3.3. Функция роста полугруппы А, заданной множеством порождающих элементов М = {а, 6} и одним определяющим соотношением bab = aba, равна Fn+2 — 1.

Зависимость количества классов эквивалентности от количества букв в слове п, 3 < п < 10, приведена в следующей таблице.

Таблица 1. Количество классов эквивалентности слов длины п, 3 < 71 < 10, порожденных соотношениями слов длины три.

п 3 4 5 6 7 8 9 10

а(п) 7 12 20 33 54 88 143 232

Р(п) 7 12 21 37 65 114 200 351

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

Всего слов длины 2 существует 4. Из них можно составить 6 соотношений. Число способов выбрать 2 соотношения из 6 возможных равно С| = 15 . Из 15 возможных систем из двух двухбуквенных соотношений достаточно рассмотреть лишь следующие 4 системы, остальные будут им эквивалентны:

[ аа = аЬ | аа = аЬ „ | аа = аЬ \ аа = ЬЬ 1.1. 1 1.2. { 1.3. { 1.4. ^

[ аа = Ьа [ аа = ЬЬ [ Ьа = ЬЬ аЬ = Ьа

Предложение 4.1.1. Если полугруппа А задана множеством порождающих элементов М = {а,Ь} и множеством определяющих соотношений 1.1, то число классов эквивалентности на множестве Мп равно двум. Первый класс состоит из одного слова Ь...Ь, число слов во втором классе эквивалентности,

в который входят все остальные слова длины п, равно 2" — 1. Канонические слова в классах эквивалентности: Ъ...Ь и а...а.

Предложение 4.1.2. Если полугруппа А задана множеством порождающих элементов М = {а, Ь} и мнол<еством определяющих соотношений 1.2, то все слова длины п будут лежать в одном классе. Каноническое слово - о...а, число слов в классе - 2П.

Предложение 4.1.3. Если полугруппа А задана мнолсеством порождающих элементов М = {а, Ь} и множеством определяющих соотношений 1.3, то число классов эквивалентности на множестве Мп равно двум. Число слов в каждом классе одинаково и равно 2"-1. Канонические слова в классах эквивалентности - а...а и Ъа...а.

Предложение 4.1.4. Если полугруппа А задана множеством порождающих элементов М = {а, Ь} и множеством определяющих соотношений 1.4, то число классов эквивалентности на множестве М" равно двум. Число слов в каждом классе одинаково и равно 2"-1. Канонические слова в классах эквивалентности - а...а и а...аЬ.

Также были рассмотрены все системы из трех двухбуквенных соотношений. Их С| = 20 штук.

{

аа = аЪ

аа = аЬ

2.1. < аа = Ьа 2.2. аа = Ьа 2.3. < аа = Ъа 2.4. аа = Ьа

аЬ = Ьа

Ьа — ЬЬ

аа = ЬЬ \ аа = ЬЬ аа = ЬЪ

2.17. аЬ = Ьа 2.18. < аЬ = Ъа 2.19. аЬ = ЬЪ 2.20. аЬ = ЬЬ ^ Ъа = ЬЬ Ьа = ЬЬ

Предложение 4.2.1. Если полугруппа А задана множеством порождающих элементов М = {а, Ъ} и множеством определяющих соотношений 2.2 либо 2.20, то число классов эквивалентности на множестве Мп равно двум.

Предложение 4.2,2. Если полугруппа А задана множеством порождающих элементов М = {о,Ь} и любым множеством определяющих соотношений, приведенным выше, кроме 2.2 и 2.20, то все слова длины п будут лежать в одном классе.

В конце четвертой главы были рассмотрены системы, состоящие из одного двухбуквенного и одного трехбуквенного соотношения. Всего таких систем 168, но достаточно рассмотреть лишь 17 из них, остальные будут им эквивалентны. В трех случаях второе соотношение является следствием первого, поэтому число классов эквивалентности на полугруппе А будет таким же, как и в случае одного двухбуквенного соотношения, а именно, п +1. В остальных 14 случаях число классов эквивалентности равно единице, двум или трем.

Автор выражает глубокую благодарность своему научному руководителю, доктору физико-математических наук, профессору Кожухову Игорю Борисовичу за постановку задач, детальное обсуждение результатов работы и всестороннюю поддержку.

ВЫВОДЫ

Таким образом, в диссертационной работе были исследованы конгруэнции свободной двупорожденной полугруппы, порожденные всевозможными парами слов длины два, длины три, а также совокупностями пар слов длины два и три, и получены следующие результаты:

1. Описаны конгруэнции свободной полугруппы над двухбуквенным алфавитом, порожденные одним определяющим соотношением, представляющим собой равенство слов длины два. Описан состав классов эквивалентности таких конгруэнций и найдены мощности классов. Доказано, что функция роста таких полугрупп равна п + 1.

2. Описаны конгруэнции свободной полугруппы над двухбуквенным алфа-

витом, порожденные одним определяющим соотношением, представляющим собой равенство слов длины три. Для некоторых таких конгруэнций описан состав классов эквивалентности и найдены мощности классов. Доказано, что:

• Функция роста полугруппы над двухбуквенным алфавитом, заданной одним из определяющих соотношений aab = ааа, aab = aba, aab = abb, aab = baa, aab = bab, aab = bba, abb = ааа, удовлетворяет рекуррентному соотношению a(n) = a(n — 1) + a(n — 2) 4-1.

• Функция роста полугруппы над двухбуквенным алфавитом, заданной определяющим соотношением aba = ааа, удовлетворяет рекуррентному соотношению ¡3{п) = 2/3(п - 1) - /3(п - 2) + /3(п - 3).

• Функция роста полугруппы над двухбуквенным алфавитом, заданной одним из определяющих соотношений bab = ааа, bab = aba, bbb = ааа, равна Fn+2 — 1, где Fn - n-oe число Фибоначчи.

3. Описаны конгруэнции свободной полугруппы над двухбуквенным алфавитом, порожденные совокупностями пар слов длины два и три. Описан состав классов эквивалентности таких конгруэнций и найдены мощности классов. Доказано, что количество классов эквивалентности равно либо п 4- 1, либо константе (единице, двум или трем).

РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ

Публикации в журналах, входящих в список ВАК

[1 ] Кудрявцев а, Л. А. Функции роста и мощности классов некоторых дву-порожденных полугрупп / Л. А. Кудрявцева // Вестник Московской государственной академии делового администрирования. Серия Философские, социальные и естественные науки. №1(13), 2012, с. 103-115.

[2 ] Кудрявцева, Л. А. О конгруэнциях двупорожденного моноида / Л. А. Кудрявцева // Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика. Том 10, выпуск 1, 2010, с. 14-18.

Публикации в прочих изданиях

[3 ] Кудрявцева, Л. А. О конгруэнциях свободной полугруппы, порожденной несколькими соотношениями слов длины два и три / JI. А. Кудрявцева // МИ ЭТ. - Москва, 2010. 27с. Деп. в ВИНИТИ 20.10.10, № 608-В2010.

[4 ] Кудрявцева, Л. А. Об эквивалентности слов двухбуквенного алфавита, порождаемой равенствами трехбуквенных слов / Л. А. Кудрявцева // Моделирование, алгоритмизация и программирование при проектировании информационно-управляющих систем. Сборник научных трудов под ред. д.т.н., проф. В.А. Бархоткина. - Москва, 2008, с. 96-103.

[5 ] Кудрявцева, Л. А. О количестве классов эквивалентности слов двухбуквенного алфавита / Л. А. Кудрявцева // Системный анализ и информационно-управляющие системы. Сборник научных трудов под ред. д.т.н., проф. В.А. Бархоткина. - Москва, 2006, с. 121-126.

[6 ] Кудрявцева, Л. А. Операция умножения на полугруппах слов канонической формы / Л. А. Кудрявцева // Микроэлектроника и информатика - 2007. Тезисы докладов 14-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов. - Москва, 2007, с. 152.

[7 ] Кудрявцева, Л. А. Об однородных конгруэнциях свободной двупорож-денной полугруппы / Л. А. Кудрявцева // Современные проблемы дифференциальной геометрии и общей алгебры. Тезисы докладов Международной научной конференции, посвященной 100-летию со дня рождения профессора В. В. Вагнера. - Саратов: Издательство Саратовского университета, 2008, с. 119-121.

[8 ] Кудрявцев а, Л. А. О конгруэнциях на полугруппе, порожденных соотношением трехбуквенных слов / Л. А. Кудрявцева // Математика, информатика, их приложения и роль в образовании. Тезисы докладов Российской школы-конференции с международным участием. - Москва, 2009, с. 225-227.

[9 ] Кудрявцева, Л. А. О числе классов эквивалентности конгруэнции, порожденной соотношением / Л. А. Кудрявцева // Материалы Международного молодежного научного форума "Ломоносов-2010"[Электронный ресурс]. - Москва: МАКС Пресс, 2010.

[10 ] Кудрявцева, Л. А. Конгруэнции конечнопорожденных полугрупп / Л. А. Кудрявцева // Алгебра и теория чисел: современные проблемы и приложения. Материалы 7-й Международной конференции, посвященной памяти профессора А. А. Карацубы. - Тула: Издательство Тульского государственного педагогического университета им. Л.Н. Толстого, 2010, с. 109-110.

Подписано в печать:

Заказ мЗУГираж 100 экз. Уч.-изд.л. ^Формат 60x84 1/16.

Отпечатано в типографии ИПК МИЭТ.

124498, Москва, Зеленоград, проезд 4806, д.5, МИЭТ.

61 12-1/1128

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «МИЭТ»

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

КУДРЯВЦЕВА ЛИКА АЛЕКСАНДРОВНА

ФУНКЦИЯ РОСТА НЕКОТОРЫХ ДВУПОРОЖДЕННЫХ ПОЛУГРУПП

01.01.06 - математическая логика, алгебра и теория чисел

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

Научный руководитель - доктор физико-математических наук,

профессор И. Б. Кожухов

Москва, 2012

Оглавление

Введение..............................................................................................4

Глава 1. Предварительные сведения..................................................................15

1.1. Теория переписывающих систем..........................................................15

Глава 2. Функции роста и мощности классов полугруппы над двухбуквенным алфавитом, порожденной одним соотношением слов длины два.....................................................................................................22

2.1. Соотношения слов длины два..............................................................22

2.2. Соотношение aa = ab.........................................................................24

2.3. Соотношение ab = ba.........................................................................25

2.4. Соотношение аа = ЪЪ.........................................................................26

2.5. Некоторые замечания........................................................................32

Глава 3. Функции роста и мощности классов полугруппы над двухбуквенным алфавитом, порожденной одним соотношением слов длины три......................................................................................................38

3.1. Соотношения слов длины три..............................................................38

3.2. Соотношение bbb = ааа.......................................................................43

3.3. Соотношение bab = ааа.......................................................................49

3.4. Соотношение bab - aba.......................................................................54

3.5. Мощность классов полугруппы А над алфавитом М, порожденной соотношением aab = ааа..........................................................................60

3.6. Мощность классов полугруппы А над алфавитом М, порожденной соотношением bbb = ааа......................................................................................62

3.7. Некоторые замечания.......................................................................65

Глава 4. Количество и мощности классов эквивалентности полугруппы над двухбуквенным алфавитом, заданной несколькими соотношениями слов длины два и три..................................................................................................68

4.1. Полугруппы, заданные двумя соотношениями слов длины два......................................................................................................................................68

4.2. Полугруппы, заданные тремя соотношениями слов длины два.....................................................................................................72

4.3. Полугруппы, заданные двумя соотношениями слов длины два и три............74

Список литературы................................................................................92

Введение

Общая характеристика работы

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

Если полугруппа А задана множеством порождающих элементов М и множеством определяющих соотношений Е, то проблема равенства слов для полугруппы А состоит в описании алгоритма, который определяет, представляют ли два слова -ю^^еМ* один и тот же элемент полугруппы А. (Здесь М* -свободный моноид над алфавитом М). Если такой алгоритм существует, то проблема равенства слов называется разрешимой; если доказано, что такого алгоритма нет, то алгоритмическую проблему называют неразрешимой. А. А. Марков [22] и Э. Л. Пост [23] в 1947 году независимо установили алгоритмическую неразрешимость проблемы равенства слов для некоторых конечно определённых полугрупп. Основные сведения о теории полугрупп можно найти в книгах Е. С. Ляпина [3], А. Клиффорда и Г. Престона [4].

При работе с образующими элементами и определяющими соотношениями часто возникают чисто комбинаторные вопросы. Эти вопросы связывают алгебру с комбинаторикой и дискретной математикой. Комбинаторным проблемам,

связанным со словами, посвящена книга А. М. Шура [25], а также большое количество работ, например: работа Г. Лаллемана [20] о проблеме равенства слов, работы Р. Бука [2] и С. Рэтхолл [10] о полугруппах, заданных одним определяющим соотношением, работа Ю. Матиясевича [21] о полугруппах, заданных несколькими определяющими соотношениями.

Данная диссертация посвящена изучению полугрупп, заданных множеством порождающих элементов М = {а,Ь} из двух элементов а и Ъ, и одним или несколькими определяющими соотношениями, представляющим собой равенство двух слов одинаковой длины.

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

Функцией роста конечно порожденной полугруппы А относительно множества порождающих элементов М, |М|<оо, мы будем называть функцию /м : N —> N, сопоставляющую числу п е N число всех различных элементов полугруппы А, записываемых словами длины п в алфавите М. Это немного отличается от определений, приведенных в статье Л. Н. Шеврина [26, §2], или в монографии В. А. Уфнаровского [27].

Цели и задачи исследования данной работы заключаются в определении функции роста полугруппы А, заданной множеством порождающих элементов М = {а,Ъ} и одним или несколькими соотношениями слов длины два и три, мощности классов эквивалентности, а также в описании самих классов.

Методы исследования. В работе используются методы и результаты теории полугрупп, теории графов, теории переписывающих систем или TRS (Term Rewriting System), а также некоторые методы перечислительной комбинаторики.

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

1. Описаны конгруэнции полугрупп над двухбуквенным алфавитом, заданных одним определяющим соотношением, представляющим собой равенство слов длины два. Найдены функции роста таких полугрупп, мощности классов эквивалентности и общий вид слов в каждом классе.

2. Описаны конгруэнции полугрупп над двухбуквенным алфавитом, заданных одним определяющим соотношением, представляющим собой равенство слов длины три. Найдены функции роста таких полугрупп. Для некоторых из этих полугрупп найдены мощности классов эквивалентности и общий вид слов в каждом классе.

3. Описаны конгруэнции полугрупп над двухбуквенным алфавитом, заданных двумя двухбуквенными соотношениями, тремя двухбуквенными соотношениями, а также одним двухбуквенным и одним трехбуквенным соотношением. Найдены функции роста таких полугрупп, мощности классов эквивалентности и общий вид слов в каждом классе.

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

опирающимися на методы алгебраической теории полугрупп и комбинаторные методы.

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

Апробация результатов. Основные результаты диссертации докладывались на семинаре «Кольца и модули» кафедры высшей алгебры МГУ; на конференциях «Микроэлектроника и информатика» МГИЭТ (Москва, Россия, 2007г, 2008г.); на Международной научной конференции, посвященной 100-летию со дня рождения профессора В.В. Вагнера СГУ (Саратов, Россия, 2008г.); на Российской школе-конференции с международным участием РУДН (Москва, Россия, 2009г.); на 17-ой Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов» МГУ (Москва, Россия, 2010г.), где доклад был отмечен как лучший доклад в секции «Математика и механика»; на 7-ой Международной конференции «Алгебра и теория чисел: современные проблемы и приложения» ТГПУ (Тула, Россия, 2010г.).

Публикации. По теме диссертации опубликовано 10 работ ([32] - [41]), из них 2 статьи ([37], [38]) в журналах из списка ВАК.

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

Структура и объем диссертации. Диссертация состоит из оглавления, введения, четырех глав и списка литературы. Полный объем диссертации - 96 страниц, библиография включает 41 наименование.

Содержание работы

В первой главе изложены предварительные сведения, основные определения и результаты теории переписывающих систем (Term Rewriting Systems). Теория переписывающих систем является удобным инструментом для нахождения функций роста групп и полугрупп. Например, в работе Р. И. Григорчука [28] получена формула для выражения числа допустимых слов, т. е. слов, не содержащих вхождения запрещенных подслов. Эта формула может быть применена для вычисления функций роста групп и полугрупп, см., например, работу М. Д. Мамагани [29]. В работе М. Д. Мамагани [30] была построена полная конечная система переписывающих правил для групп Коксетера.

Во второй главе полностью разобраны полугруппы, заданные одним определяющим соотношением, представляющим собой равенство слов длины два. Всего двухбуквенных соотношений существует 6. С точностью до инверсии и замены букв а и Ъ местами, принципиально разными будут лишь следующие 3 соотношения:

aa-ab, аЪ = Ъа и aa = bb . (2.2)

Каноническим словом в данном классе эквивалентности будем называть слово, наименьшее относительно лексикографического порядка. Если weM", то через K(w) обозначим класс эквивалентности, в котором лежит слово w. Пусть | K{w) | - число элементов в классе эквивалентности K(w). Число элементов в классе эквивалентности будем также называть мощностью этого класса.

Предложение 2.1. Функция роста полугруппы А, заданной множеством образующих элементов М = {а,Ь} и одним определяющим соотношением аа = аЪ,

равна п +1. Канонические слова в каждом классе имеют, вид м?1 = Ь'а"~', / = 0,1,...,п. Число элементов в каждом классе равно \ К(м^) |= 2"-'4, г = 0,1,...,п -1 и \ К{м?п) |= 1.

Предложение 2.2. Функция роста полугруппы А, заданной множеством образующих элементов М = {а,Ь} и одним определяющим соотношением аЬ = Ьа,

равна п +1. Канонические слова в каждом классе имеют вид =а"~'Ь', / = 0,1,...,п. Число элементов в каждом классе равно | КЫ,) |= С'п, г = ОД,...,«.

Предложение 2.3. Функция роста полугруппы А, заданной множеством образующих элементов М = {а,Ь} и одним определяющим соотношением аа-ЪЪ, равна п +1. Канонические слова в каждом классе имеют вид:

где и - либо пустое слово, либо слово, состоящее из одной буквы b, либо слово, состоящее из чередующихся букв b и а, начиная с b.

Сложнее оказалось получить формулу для числа элементов в каждом классе эквивалентности, порожденном соотношением аа-ЪЬ. В главе 2 приведено два доказательства следующей теоремы: первое основано на индукции по п, второе использует комбинаторную формулу Вандермонда.

Теорема 2.1. Обозначим через а(п,к) число слов в классе эквивалентности

слов длины п, содержащих слово wk=ak - и, (0<к<п), где и - либо пустое слово

(при к = п), либо состоящее из одной буквы b (при k = n-l), либо состоящее из чередующихся букв b и а, начиная с b. Тогда

В заключительной части главы 2 показано, что количество классов эквивалентности слов длины п над двухбуквенным алфавитом в случаях действия

w,: = а' - и, i = 0,1,...,п,

(2.3)

(2.4)

соотношений aa = ab и ab = Ъа может быть найдено как число слов длины п, не содержащих подслова аЪ. Для соотношения аа = ЪЪ показано, что количество классов эквивалентности слов длины п над двухбуквенным алфавитом может быть найдено как число слов длины п, не содержащих подслов bb и baa одновременно. Подсчет количества слов длины п, не содержащих одного определенного подслова, уже производился некоторыми авторами. Подобные расчеты сделаны, например, в работах Р. Дорословацки [12] и Р. Дорословацки, О. Марковица [13] для подслов длины три. Для подсчета количества слов, не содержащих одновременно двух или нескольких подслов, был использован метод трансфер-матрицы (см. Р. Стенли [14], С. Хейбач и Т. Мансур [15]). Подсчет количества слов длины п, не содержащих подслов bb и baa одновременно, сделан в конце второй главы.

В третьей главе разобраны полугруппы, заданные одним определяющим соотношением, представляющим собой равенство слов длины 3. С точностью до инверсии слова и перемены букв а и Ъ местами, достаточно рассмотреть лишь 11 соотношений, представляющих собой равенство двух трехбуквенных слов: ааЪ = ааа , aab - aba , aab = abb , aab = baa, aab = bab, aab = bba, aba - aaa , abb = aaa, bab = aaa, bab - aba, bbb = aaa. Показано, что функция роста полугруппы, заданной множеством порождающих элементов М = {а,Ь} и одним из соотношений aab = aaa, aab - aba, aab = abb , aab = baa, aab = bab, aab = bba, abb = aaa, удовлетворяет рекуррентному соотношению a(n) = a(n -1) + a{n - 2) +1; функция роста полугруппы, заданной множеством порождающих элементов М = {а, Ь} и соотношением aba = ааа, удовлетворяет рекуррентному соотношению /3{п) = 2Р(п -1) - Р(п - 2) + ¡3{п - 3). Также доказаны следующие теоремы:

Теорема 3.1. Функция роста полугруппы А, заданной множеством

порождающих элементов М = {а,Ь} и одним определяющим соотношением bbb = acta, равна Fn+2 -1, где Fn - п-ое число Фибоначчи.

Теорема 3.2. Функция роста полугруппы А, заданной множеством

порождающих элементов М = {а,Ь} и одним определяющим соотношением ЪаЪ = ааа, равна Fn+2 -1.

Теорема 3.3. Функция роста полугруппы А, заданной множеством

порождающих элементов М = {а,Ь} и одним определяющим соотношением bab - aba, равна Fl¡+2 -1.

Зависимость количества классов эквивалентности от количества букв в слове п, 3 < п < 10, приведена в следующей таблице.

Таблица 3.1. Количество классов эквивалентности слов длины 3<и<10, порожденных соотношениями слов длины три.

п 3 4 5 6 7 8 9 10

а(п) 7 12 20 33 54 88 143 232

т 7 12 21 37 65 114 200 351

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

Всего слов длины 2 существует 4. Из них можно составить 6 соотношений.

Число способов выбрать 2 соотношения из 6 возможных равно С62 = 15. Из 15

возможных систем из двух двухбуквенных соотношений достаточно рассмотреть

лишь следующие 4 системы, остальные будут им эквивалентны:

„ „ „ \аа = аЬ , „ ^ \аа = аЬ „ „ „ \аа = аЪ „ „ „ Гад = ЬЬ 4.3.4.3.2.{ 4.3.3.^ 4.3.4.<^

[аа = 6а [аа = ЬЪ [Ьа = ЬЬ [аЪ = 6а

Предложение 4.1.1. Если полугруппа А задана множеством порождающих элементов М = {а,Ь} и множеством определяющих соотношений 4.3.1, то число классов эквивалентности на множестве Мп равно двум. Первый класс состоит из одного слова Ъ...Ъ, число слов во втором классе эквивалентности, в который входят все остальные слова длины п, равно 2" -1. Канонические слова в классах эквивалентности: Ъ...Ь и а...а.

Предложение 4.1.2. Если полугруппа А задана множеством порождающих элементов М = {а,Ь} и множеством определяющих соотношений 4.3.2, то все слова длины п будут лежать в одном классе. Каноническое слово - а...а, число слов в классе - 2".

Предложение 4.1.3. Если полугруппа А задана множеством порождающих элементов М = {а,Ь} и множеством определяющих соотношений 4.3.3, то число классов эквивалентности на множестве Мп равно двум. Число слов в каждом классе одинаково и равно 2"~х. Канонические слова в классах эквивалентности -а...а и Ьа...а.

Предложение 4.1.4. Если полугруппа А задана множеством порождающих элементов М = {а,Ь} и множеством определяющих соотношений 4.3.4, то число классов эквивалентности на множестве М" равно двум. Число слов в каждом

классе одинаково и равно 2 . Канонические слова в классах эквивалентности -а...а и а...аЬ.

Также были рассмотрены все системы из трех двухбуквенных соотношений. Их С\ = 20 штук.

4.4.1.

4.4.5.

4.4.9.

4.4.13

4.4.17.

аа = аЪ аа = Ъа 4.4.2. аа = ЬЬ

аа = аЪ

аа = ЬЬ 4.4.6. аЪ = Ьа

аа = аЪ

аЬ = Ъа 4.4.10.

Ьа = ЬЬ

аа = Ьа

аа = ЬЬ 4.4.14. Ьа = ЬЬ

аа = ЬЬ

аЬ = ¿¿г 4.4.18.

аЬ = ЬЬ

аа = аЬ

■\аа = Ъа 4.4.3 аЬ = Ьа

аа = аЬ

аа = ЬЬ 4.4.7. < аЬ - ЬЬ

аа = аЬ

аЬ = ЬЬ 4.4.11. Ьа = ЪЪ

аа = Ьа

аЪ = Ъа 4.4.15.

аЬ = ЬЬ

аа = ЬЬ

аЬ = Ьа 4.4.19. Ъа = ЬЬ

аа = аЬ

аа = Ьа 4.4.4.

аЬ =

аа = аЪ аа = ЬЬ Ьа = ЬЬ

4.4.8.

аа = 6а

аа = 66 4.4.12. < аЪ = 6а

аа = Ьа

аЬ = Ьа 4.4.16. ■ Ьа - ЬЬ

аа = 66

аб = ЬЬ 4.4.20. Ьа = ЬЬ

аа = аб аа = Ъа Ьа = ЬЬ

аа = аЬ аЬ - Ьа аЬ = ЬЬ

аа - Ьа аа = ЬЬ аЬ = ЬЬ

аа = Ьа аЪ = ЬЬ Ьа = ЬЬ

аЬ = 6а аб = ЬЬ Ъа = ЬЬ

Предложение 4.2.1. Если полугруппа А задана множеством порождающих элементов М = {а, 6} и множеством определяющих соотношений 4.4.2 либо 4.4.20,

то число классов эквивалентности на множестве М" равно двум.

Предложение 4.2.2. Если полугруппа А задана мно�