Универсальные рациональные множества в группах

• Автор: Григоренко, Ольга Викторовна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Омск
• Количество страниц: 48 с. : ил.

Содержание
Введение
Глава 1. Предварительные сведения
Глава 2. Универсальные рациональные языки
2.1. Некоторые свойства универсальных рациональных языков
2.2.Некоторые нерациональные языки
Глава 3. О существовании универсальных рациональных
структур на группах
3.1. Проблема существования универсальной рациональной структуры на конечно порождённых группах
3.1. Проблема Герстена-Шорта
Глава 4. Применение рациональности и симметрии при исследовании различных систем уравнений
4.1. Бесконечные системы уравнений в группах
4.2. Симметричные системы линейных уравнений
Литература
Введение
Актуальность темы. Изучение конечных автоматов и рациональных (регулярных, распознаваемых) множеств началось в 50-х годах XX века в связи с началом развития вычислительной техники. В настоящее время конечные автоматы применяются при моделировании процессов в различных областях интеллектуальной деятельности человека, например в лингвистике, экономике, философии, биологии. В математике конечные автоматы и рациональные множества - это уже хорошо известные и привычные объекты. В основном они сформировались в рамках теории полугрупп.
Исследования рациональных множеств группах, как правило, проводились методами комбинаторной теории групп. В комбинаторной теории групп основными объектами являются слова в групповом алфавите, отношения эквивалентности между словами, а также свойства слов, инвариантные относительно некоторых преобразований. Комбинаторная теория групп исследует группы, заданные образующими и определяющими соотношениями. Основы комбинаторной теории групп изложены в классических монографиях Линдона, Шуппа [5] и Магнуса, Карраса, Солитера [6] под общим названием "Комбинаторная теория групп".
Значительная часть проведённых исследований в рассматриваемой области посвящена рациональным языкам (рациональным множествам в свободных моноидах). Здесь можно отметить монографии Гилмана [17], Флойда и Бигеля [15], Харрисона [18], Ревеза [19]. Отметим также фундаментальный труд по автоматным группа Эпстина, Кэннона, Холта, Леви, Патерсона и Терстона [14] и монографию по конечным автоматам Эйленберга [13].
Класс рациональных (регулярных, распознаваемых) подмножеств произвольного моноида М классически определяется как минимальный класс, содержащий все конечные подмножества М и замкнутый относительно
рациональных операций, то есть объединения, умножения и порождения подмоноида. Взяв в качестве моноида М группу С, получаем определение рациональных подмножеств в группе С
Конечный автомат — это конечный ориентированный граф, в котором выделена некоторая вершина, называемая начальной, и подмножество вершин, называемых конечными (или допустимыми). Рёбра графа имеют метки - элементы некоторого множества (моноида или группы). Проходя по некоторому пути из начальной вершины в конечную и перемножая последовательно метки рёбер, получаем некоторый элемент моноида (группы), который называется допустимым относительно автомата. Множество всех допустимых элементов называется множеством, допустимым относительно автомата.
Исследования рациональных множеств тесно связаны с изучением конечных автоматов. Известно (см. [17]), что любое допустимое относительно автомата множество является рациональным, и наоборот, любое рациональное множество задаётся конечным автоматом.
Идея использования конечных автоматов актуальна для теории групп. Как правило, в рамках этого подхода (см.[ 14], [16]) рассматриваются рациональные подмножества свободных моноидов, а связь с группой реализуется с помощью понятия "выбор порождающих". Эта связь не всегда адекватно отражает то, что происходит непосредственно в группе. Так в рамках данной теории определение рационального подмножества группы зависит от рациональной структуры на группе и не инвариантно относительно её выбора. Кроме того, оно имеет смысл лишь в конечно порождённых группах. Тем более естественно изучать рациональные подмножества групп в смысле непосредственного определения.
Дальнейшее изучение рациональных множеств в группах проводилось
В.А. Романьковым и его учениками Г.А. Баженовой, М.Ю. Недбаем (см. [1] -[3], [7]-[9], [10], [20]). В этих работах использовалось определение рациональных множеств через рациональные операции, а также не

Итак, пусть I- универсальная по подгруппам рациональная структура. Пусть дана кратчайшая по числу шагов схема построения Ь из конечных
языков.
Пусть на каком-то шаге построения Ь из конечных языков впервые
появляется не конечно линейный язык. Как и в доказательстве теоремы 1 возьмем два случая.
Пусть К, как в лемме 9 а язык ги’со для некоторых и
элементов и,у, как в лемме 9, лежит в Выберем такой базис а,Ь группы Z2, относительно которого с = ак,Ь = Ь1 ,к,1 > 1, где независимые элементы с = /л{и<Л = //(у) имеют тот же смысл, что и в лемме 9. Пусть / = р(гсо) = арЬч ,р,<7 ег.
Пусть сначала р>1. Тогда р(ир‘учк)= /1к. Легко видеть, что полный прообраз в ги'х'со циклической группы р(/) совпадает с множеством ф. гК (о , где К из леммы 9 с теми же значениями параметров к,1. Получили
противоречие между нерациональностью К и, следовательно, по лемме 1 -/К со и гипотетической универсальностью по подгруппам Ь.
Заметим теперь, что условия /?, Рассмотрим теперь ситуацию, в которой К появляется из леммы 10. Итак, пусть Ь содержит не конечно линейный подъязык г,12<у, где ЯЗЫКИ /,/, Ь? еще конечно линейны. Как и в разборе соответствующего случая теоремы 1, представим минимальным образом языки £/, £? в виде объединений линейных языков, соответствующих максимальным циклическим подгруппам группы Zi. Найдем среди них языки Ц и произведение которых £,'/.2 не конечно линейно. □