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

• Автор: Кудрявцева, Лика Александровна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 96 с. : ил.

Оглавление
Введение
Глава 1. Предварительные сведения
1.1. Теория переписывающих систем
Глава 2. Функции роста и мощности классов полугруппы над двухбуквенным алфавитом, порожденной одним соотношением слов длины два
2.1. Соотношения слов длины два
2.2. Соотношение aa
2.3. Соотношение ab-ba
2.4. Соотношение аа
2.5. Некоторые замечания
Глава 3. Функции роста и мощности классов полугруппы над двухбуквенным
алфавитом, порожденной одним соотношением слов длины

3.1. Соотношения слов длины три
3.2. Соотношение ЪЪЪ
3.3. Соотношение bob
3.4. Соотношение bab
3.5. Мощность классов полугруппы А над алфавитом М, порожденной соотношением ааЪ
3.6. Мощность классов полугруппы А над алфавитом М, порожденной соотношением bbb

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

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

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

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

разобьем на 3 группы. К первой отнесем слова, оканчивающиеся на аа, ко второй -слова, оканчивающиеся на аЬ, к третьей - слова, оканчивающиеся на Ьа. Рассмотрим граф с тремя вершинами, соответствующими каждой из этих групп. Каждое слово длины к +1 получается из слова длины к приписыванием справа буквы а или Ь. Если из слова, соответствующего одной из вершин, можно получить другое допустимое слово приписыванием справа буквы а или Ь, то проведем из данной вершины дугу. В результате получим граф /)0, изображенный на рис. 2.1. Основные сведения из теории графов можно найти в [17] и [18].
Рис. 2.1. Граф Ц
Вершина 1. Слова, оканчивающиеся на аа.
2. Слова, оканчивающиеся на аЬ.
3. Слова, оканчивающиеся на Ьа.
Указанные выше 3 вершины графа соединяются следующими дугами: (1,1), (1,2), (2,3), (3,2). Матрица смежности этого графа имеет вид:

О 1 О4 О

О 1 О
Сумма элементов в /'-й строке матрицы Я есть число допустимых слов длины 3, получающихся из допустимых слов длины 2, соответствующих г'-й вершине. Таким образом, сумма всех элементов матрицы Я даст число допустимых слов длины 3.
Вычислим степени этой матрицы со 2-ой по 5-ую.