Некоторые свойства рациональных подмножеств в группах

• Автор: Недбай, Максим Юрьевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Омск
• Количество страниц: 55 с.

Содержание
Введение

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

Глава 2. Проблема вхождения для рациональных подмножеств в группах.

§ 2.1. Проблема вхождения для свободных и абелевых групп .

§ 2.2. Проблема вхождения для групповых конструкций .

Глава 3. Высота и кофинитность.

§ 3.1. Высота рационального множества

§ 3.2. Рациональность кофинитных подмножеств

Глава 4. Полугруппа коцечн{д^*]и,кононечных подмножеств группы. '•**»;?

§ 4.1. Основные свойства 5((7) и АиЬ8{С)

§ 4.2. Формульность подмножеств К^г С^> .
Литература

Введение.
В данной работе мы исследуем класс рациональных подмножеств в группе. Класс рациональных подмножеств произвольного моноида М определяется стандартным образом как минимальный класс, содержащий все конечные подмножества М и замкнутый относительно рациональных операций, то есть объединения, умножения и порождения подмоноида. Беря в качестве моноида М группу С, получаем определение рациональных подмножеств в в.
Конечный автомат - это конечный направленный граф, в котором выделена некоторая вершина, называемая начальной, и подмножество вершин, называемых конечными (или допустимыми). На ребрах графа пишутся метки - это элементы некоторого множества (моноида или группы). Проходя по некоторому пути из начальной вершины в конечную, мы последовательно записываем метки с тех ребер графа, через которые проходим. Таким образом, мы получаем некоторый элемент моноида (или группы соответственно). Множество всех элементов, полученных описанным методом, называется допустимым относительно автомата. Это множество всегда рационально.
Любое рациональное множество задается конечным автоматом. Таким образом, исследование рациональных множеств тесно связано с изучением конечных автоматов.
Вкратце описывая результаты нашего исследования, можно сказать следующее. В этой работе мы доказываем алгоритмическую разрешимость проблемы вхождения в рациональные подмножества для свободных групп и конечно-порожденных абелевых групп. Показываем, что разрешимость проблемы вхождения в рациональные подмножества переносится на свободные произведения групп и не переносится на прямые произведения и расширения. Утверждается также, что в группе, содержащей свободную неабелеву подгруппу, существуют рациональные множества любой высоты. Устанавливается рациональность кофинитных множеств для некоторых классов групп (групп с конечным ните-вым базисом, полициклических). Замечено, что рациональности

множества С?1 для конечко-определенной группы (7 достаточно для разрешимости в (7 проблемы равенства. Определены некоторые свойства полугруппы 5(С) конечных и коконечных подмножеств группы (7, а также группы автоморфизмов Аи1Б(0). Введено понятие характеристики элемента из Б (О) и доказана формульность классов множеств с одинаковой характеристикой для широкого класса групп.
Скажем теперь несколько слов о разделе алгебры, в котором проводились исследования.
Относительно исследований рациональных множеств следует заметить, что этот раздел алгебры является частью более широкого, а именно, комбинаторной теории групп. Как известно, в комбинаторной теории групп основными объектами при изучении групп являются слова в групповом алфавите, отношения эквивалентности между словами, а также свойства слов, инвариантные относительно некоторых преобразований. Комбинаторная теория групп (в отличие от общей теории групп) исследует группы, заданные образующими и определяющими соотношениями. Многие важные вопросы теории групп удалось решить с помощью используемых в этой теории комбинаторных методов. Это, например, всем известные результаты Нильсена-Шрайера о свободных группах.
Основы комбинаторной теории групп изложены в классических монографиях Линдона, Шуппа [9], и Магнуса, Карраса, Солитера [10] под общим названием ’’Комбинаторная теория групп”.
Возвращаясь к рациональным множествам, мы можем сказать, что они изучаются уже достаточно долго. Правда, основная часть исследований посвящена так называемым рациональным языкам (рациональным множествам в свободных моноидах). Здесь мы можем отметить монографии Гилмана [23], Флойда и Бигеля [20], Харрисона [25], Хопкрофта и Уллмана [27], [28], Гинзбурга [8], Ре-веза [33]. Отметим также фундаментальный труд по автоматным группам Эпстина, Кэннона, Холта, Леви, Патерсона и Терстона [19] и работы по конечным автоматам Эйленберга [17], Голдстайна [24].
Наши исследования связаны с понятием рационального мно-

Рассмотрим п конечных подмножеств Z :
Р — • • • ) Iml},
Рч = {^12; I22, • • • ) Imï}, Рг — {кз, ^23) • • ■, 4гсз}>
Рп = {km кт • • • ! ^mn}>
из m элементов каждое. Поскольку Z - абелева группа, то по теореме 1.
- рациональные множества, следовательно, существуют автоматы, задающие эти множества. Рассмотрим автомат V вида
Vl=Al(lll)-B'2-B’,-...B'n U
Лц-(л2(/12) б; и
Ап-(АМ-В'А-,..В'пи
А-13 • (• • • U A.n-iA.n (/ira),
где Ai(ljk) - автомат, полученный из автомата задающего множество S(bi){ljk} заменой единицы на ребрах на элемент Ъ{ и операции ”+” на операцию группы G. Автоматы Лу получены аналогичной процедурой из автоматов для множеств {/у}-Автоматы В[ описаны выше. Нетрудно видеть, что V задает множество G{ki}. Рассмотрим теперь ’’ветку” Ai(lu) ■ В'2- Ву...В'п автомата V и заменим ее следующей:
A1(ln,hi)-B,2-B,3....BlnU
Л21 • (A2(/i2,122) ■ В'ъ’ • • • В’пи
Л22 • (Аз(1ы, 12з) • Б4 ■... В'пU
А23 • (• • • U h.2n-An(lim 12п),
где Mljlkl,lhk2) - автомат, полученный из автомата задающего множество 5(Ь){1^kiGhh) описанной выше процедурой. Тогда полученный автомат V2 задает множество G{ki,k2}. Продолжая этот процесс получим автомат для G{ki, к2,..., кт}. □