Функция роста некоторых двупорожденных полугрупп

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

Актуальность темы

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

Если полугруппа, А задана множеством порождающих элементов М и множеством определяющих соотношений Е, то проблема равенства слов для полугруппы, А состоит в описании алгоритма, который определяет, представляют ли два словаю^^еМ* один и тот же элемент полугруппы А. (Здесь М* -свободный моноид над алфавитом М). Если такой алгоритм существует, то проблема равенства слов называется разрешимойесли доказано, что такого алгоритма нет, то алгоритмическую проблему называют неразрешимой. А. А. Марков [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. Если полугруппа, А задана множеством порождающих элементов М = {а, Ь} и любым множеством определяющих соотношений, приведенным выше, кроме 4.4.2 и 4.4.20, то все слова длины п будут лежать в одном классе.

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

1. Otto F., Wrathall С. A note on Thue systems with a single defining relation // Math. Systems Theory. 1985. V. 18. P. 135−143.

2. Book R. V. A note on special Thue systems with a single defining relation // Math. Systems Theory. 1983. V. 16. P. 57−60.

3. Ляпин E. С. Полугруппы. M.: Гос. Изд-во физ.-мат. лит., 1960. 592с.

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

5. Kapur D., Narendran P. A finite Thue system with decidable word problem and without equivalent finite canonical system // Theoretical Computer Science. 1985. V. 35. P. 337−344.

6. Madlener K., Otto F. About the descriptive power of certain classes of finite string-rewriting systems // Theoretical Computer Science. 1989. V. 67. P. 143 172.

7. Book R. Thue systems as rewriting systems // Journal of Symbolic Computation. 1987. V. 3.P. 39−68.

8. Holt D., Eick В., O’Brian E. Handbook of computational group theory. Chapman and Hall, CRC Press, 2005. 496p.

9. Knuth D., Bendix P. Simple word problems in universal algebras // in: J. Leech (Ed.), Computational Problems in Abstract Algebra, Pergamon Press, New York, 1970, pp. 263−297.

10. Wrathall C. Confluence of one-rule Thue systems // Lecture Notes in Computer Science, 1992. V. 572. P. 237−246.

11. W. Kurth. Termination und Confluenz von Semi-Thue-Systems mit nur einer Regel, Dissertation, Mathematische-Naturwissenschaftliche Facultat, Technische Universitat Clausthal, Chapter 6, 1990.

12. R. Doroslovacki. 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. No. 2. P. 111 115.

13. R. Doroslovacki, Marko vie O. N-words over any alphabet with forbidden any 3-subwords // Novi Sad J. Math, 2000. V. 30. No. 2. P. 159−163.

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

15. Silvia Heubach, Toufik Mansour. Combinatorics of compositions and words // Discrete mathematics and its applications. CRC Press, 2009.-480p.

16. R. Doroslovacki. Binary sequences without 011.110 for fixed к 11 Математичкиквесник, 1994. V. 46. P. 93−98.

17. Харари Ф. Теория графов. М.: Мир, 1973.-301с.

18. Белов В. В. Теория графов. / В. В. Белов, Е. М. Воробьев, В. Е. Шаталов. М.: «Высш. школа», 1976. — 392с.

19. Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. -288с.

20. Lallement G. The word problem for Thue rewriting systems // Lecture Notes in Computer Science, 1995. V. 909. P. 27−38.

21. Matiyasevich Y. Word Problem for Thue Systems with a Few Relations // Lecture Notes in Computer Science, 1995. V. 909. P. 39−53.

22. Марков А. А., «Докл. АН СССР», 1947, T.55, № 7, с. 587−590.

23. Post E. L., «J. Symbol. Log.», 1947, V.12, № 1, p. 1−11.

24. J. W. Klop. Term rewriting systems 11 Handbook of Logic in Computer Science, Vol. 2, 1−116, Oxford Univ. Press, 2002.

25. Шур A. M. Комбинаторика слов: учеб. пособие.- Екатеринбург: Изд-во Урал, ун-та, 2003.96 с.

26. JI. Н. Шеврин. Полугруппы. В сб. «Общая алгебра», т. 2, гл. IV, сер. СМБ, -М.: Наука, 1991, с. 11−191.

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

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

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

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

31. G. Huet, «Confluent reductions: abstract properties and applications to term rewriting systems», J. ACM 27 (1980), 797−821.Работы автора по теме диссертации.

32. Кудрявцева JI. А. Операция умножения на полугруппах слов канонической формы // Микроэлектроника и информатика 2007. Тезисы докладов. Москва, 2007. С. 152.

33. Кудрявцева JI. А. Об однородных конгруэнциях свободной двупорожденной полугруппы // Современные проблемы дифференциальной геометрии иобщей алгебры. Тезисы докладов. Изд-во Саратовского университета, 2008. С. 119−121.

34. Кудрявцева JI. А. О числе классов эквивалентности конгруэнции, порожденной соотношением bab = aba II Материалы Международного молодежного форума «Ломоносов 2010» Электронный ресурс. М.: МАКС Пресс, 2010.

35. Кудрявцева Л. А. Конгруэнции конечнопорожденных полугрупп // Материалы 7-ой Международной конференции «Алгебра и теория чисел: современные проблемы и приложения». Тезисы докладов. Тула: изд-во Тул. гос. пед. ун-та им. Л. Н. Толстого, 2010. С. 109−110.

36. Кудрявцева Л. А. Функции роста и мощности классов некоторых двупорожденных полугрупп // Вестник МГАДА. 2012. № 1 (13). С. 103−115.

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

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