Введение к работе
Актуальность темы. Свободные полугруппы играют важную роль в теории полугрупп, поскольку любая полугруппа является гомоморфным образом свободной. Одним из способов задания полугруппы является задание ее с помощью образующих элементов и определяющих соотношений. В связи с этим возникает вопрос, представляют ли два различных слова один и тот же элемент полугруппы. Этот вопрос известен под названием проблемы равенства слов.
Если полугруппа А задана множеством порождающих элементов М и множеством определяющих соотношений Е , то проблема равенства слов для полугруппы А состоит в описании алгоритма, который определяет, представляют ли два слова ifi, if2 Є М* один и тот же элемент полугруппы А. (Здесь М* - свободная полугруппа над алфавитом М). Если такой алгоритм существует, то проблема равенства слов называется разрешимой; если доказано, что такого алгоритма нет, то алгоритмическую проблему называют неразрешимой. А.А. Марков1 и Э. Л. Пост2 в 1947 году независимо установили алгоритмическую неразрешимость проблемы равенства слов для некоторых конечно определённых полугрупп. Основные сведения из теории полугрупп можно найти в книгах Е. С. Ляпина3, А. Клиффорда и Г. Престона4.
При работе с образующими элементами и определяющими соотношениями часто возникают чисто комбинаторные вопросы. Эти вопросы связывают алгебру с комбинаторикой и дискретной математикой. Комбинаторным проблемам, связанным со словами, посвящена монография А. М. Шура5, а также большое количество работ, например: работа Г. Лаллемана6 о проблеме равенства слов, работы Р. Бука7 и С. Рэтхолл8 о полугруппах, заданных одним определяющим соотношением, работа Ю. Матиясевича9 о полугруппах, за-
і Марков А. А., ДАН СССР, 1947, т.55, №7, с. 587-90.
2Post Е. L., J. Symbol. Logic, 1947, v.12, М, p. 1-11.
3Ляпин Е. С. Полугруппы. М.: Гос. изд-во физ.-мат. лит., 1960.
4Клиффорд А., Престон Г. Алгебраическая теория полугрупп, тт. 1, 2. М.: Мир, 1972.
5Шур А. М. Комбинаторика слов: учеб. пособие.- Екатеринбург: Изд-во Урал, ун-та, 2003.
6Lallement G. The word problem for Thue rewriting systems // Lecture Notes in Computer Science, 1995, v.909, p. 27-38.
7Book R. V. A note on special Thue systems with a single defining relation // Math. Systems Theory, 1983, v.16, p. 57-60.
8Wrathall C. Confluence of one-rule Thue systems // Lecture Notes in Computer Science, 1992, v.572, p. 237-246.
9Matiyasevich Y. Word Problem for Thue Systems with a Few Relations // Lecture Notes
данных несколькими определяющими соотношениями.
Диссертационная работа посвящена изучению полугрупп, заданных множеством порождающих элементов М = {а, Ъ] из двух элементов а и 6, и одним или несколькими определяющими соотношениями, представляющими собой равенство двух слов одинаковой длины.
В работе полностью разобраны случаи определяющих соотношений слов длины два и три. Если конгруэнция задается равенством /^-буквенных слов, то конгруэнтными могут быть только слова одинаковой длины. Поэтому будем рассматривать соответствующее отношение эквивалентности на множестве Мп слов длины п.
Функцией роста конечно порожденной полугруппы А относительно множества порождающих элементов М, \М\ < оо, мы будем называть функцию /м : N —> N, сопоставляющую числу п Є N число всех различных элементов полугруппы А: записываемых словами длины п в алфавите М. Это немного отличается от определений, приведенных в статье Л. Н. Шеврина10, 2, или в монографии В. А. Уфнаровского11.
Объектом исследования в работе являются полугруппы, заданные одним или несколькими равенствами слов длины два или три над двухбуквенным алфавитом. Нахождение функций роста таких полугрупп, мощности и строения классов эквивалентности является предметом исследования. Цель и задачи работы. Основной целью диссертационной работы является исследование полугрупп над двухбуквенным алфавитом, порожденных одним или несколькими соотношениями слов длины два и три. Для достижения цели были поставлены и решены следующие задачи:
Вычислены функции роста полугрупп над двухбуквенным алфавитом, заданных одним или несколькими соотношениями слов длины два и три.
Установлен общий вид слов в классах эквивалентности конгруэнции, порожденных одним или несколькими соотношениями слов длины два и три.
Вычислены мощности классов эквивалентности в ряде случаев. Методы исследования. В работе использованы методы теории полугрупп,
in Computer Science, 1995, v.909, p. 39-53.
10Шеврин Л. H. Полугруппы. В сб. Общая алгебра, т. 2, гл. IV, сер. СМБ, - М.: Наука, 1991, с. 11 - 191.
11 Уфнаровский В. А. Комбинаторные и асимптотические методы в алгебре, Алгебра -6, Итоги науки и техн. Сер. Соврем, пробл. мат. Фундам. направления, 57, ВИНИТИ, М., 1990, с. 5 - 177.
теории графов, теории переписывающих систем или TRS (Term Rewriting System), а также некоторые методы перечислительной комбинаторики. Научная новизна. В диссертационной работе получен ряд результатов о строении полугрупп, заданных одним определяющим соотношением длины два, одним определяющим соотношением длины три, а также несколькими определяющими соотношениями длины два и три. Полученные результаты являются новыми. Научные положения, выносимые на защиту.
Для свободной двупорожденной полугруппы описаны конгруэнции, порожденные всевозможными парами слов длины два, длины три, а также совокупностями пар слов длины два и три.
Вычислены функции роста полугрупп, порожденных двумя элементами, с соотношениями, описанными в п. 1.
Установлен общий вид слов в классах эквивалентности вышеназванных конгруэнции свободных двупорожденных полугрупп и вычислены мощности классов в ряде случаев.
Достоверность результатов проведенных исследований. Достоверность результатов, полученных в данной работе, определяется обоснованными теоретическими выкладками и строгими доказательствами, опирающимися на методы алгебраической теории полугрупп и комбинаторные методы. Практическая и теоретическая ценность. Работа носит теоретический характер. Полученные результаты могут найти применение в исследованиях теории полугрупп и в задачах компьютерной алгебры.
Апробация работы. Основные результаты и вопросы диссертации обсуждались в виде выступлений на следующих конференциях и семинарах:
Четырнадцатая всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика». Москва. 18 - 20 апреля 2007 г.;
Международная научная конференция «Современные проблемы дифференциальной геометрии и общей алгебры», посвященная 100-летию со дня рождения профессора В. В. Вагнера. Саратов. 5-7 ноября 2008 г.;
Российская школа-конференция с международным участием «Математика, информатика, их приложения и роль в образовании». Москва. 14 - 18 декабря 2009 г.;
Семнадцатая международная конференция студентов, аспирантов и молодых ученых «Ломоносов». Москва. 12 - 15 апреля 2010 г.;
Седьмая международная конференция «Алгебра и теория чисел: современные проблемы и приложения», посвященная памяти профессора А. А. Карацубы. Тула. 11-16 мая 2010 г.;
Семинары «Кольца и модули» кафедры Высшей алгебры Московского государственного университета.
Личный вклад автора. В диссертации изложены результаты, полученные автором лично. Постановка задач выполнена совместно с научным руководителем.
Публикации. По теме диссертации опубликовано 10 работ, в том числе две статьи в журналах из списка ВАК.
Объем и структура диссертации. Диссертация состоит из введения, четырех глав и списка литературы. Содержит 96 страниц машинописного текста, список литературы из 41 наименования.