Введение к работе
Актуальность темы. Изучение конечных автоматов и рациональных (регулярных, распознаваемых) множеств началось в 50-х годах XX века в связи с началом развития вычислительной техники. В настоящее время конечные автоматы применяются при моделировании процессов в различных областях интеллектуальной деятельности человека, например в лингвистике, экономике, философии, биологии. В математике конечные автоматы и рациональные множества -это уже хорошо известные и привычные объекты.
Исследования рациональных подмножеств в группах проводятся в основном методами комбинаторной теории групп. В комбинаторной теории групп основными объектами являются слова в групповом алфавите, отношения эквивалентности между словами, а также свойства слов, инвариантные относительно некоторых преобразований. Комбинаторная теория групп (в отличие от общей теории групп) исследует группы, заданные образующими и определяющими соотношениями. Основы комбинаторной теории групп изложены в классических монографиях Линдона, Шуппа [5] и Магнуса, Карраса, Солитера [6] под общим названием "Комбинаторная теория групп".
Значительная часть проведённых исследований
посвящена рациональным языкам (рациональным множествам в свободных моноидах). Здесь можно отметить монографии Гилмана [17], Флойда и Бигеля [15], Харрисона [18], Ревеза [19]. Отметим также фундаментальный труд по автоматным группам Эпстина, Кэннона, Холта, Леви, Патерсона и Терстона [14] и работу по конечным автоматам Эйленберга [13].
Класс рациональных (регулярных, распознаваемых) подмножеств произвольного моноида М определяется как минимальный класс, содержащий все конечные подмножества М и замкнутый относительно рациональных операций, то есть объединения, умножения и порождения подмоноида. Взяв в качестве моноида М группу G, получаем определение рациональных подмножеств в группе G.
Конечный автомат - это конечный ориентированный граф, в котором выделена некоторая вершина, называемая начальной, и подмножество вершин, называемых конечными (или допустимыми). Рёбра графа имеют метки — элементы некоторого множества (моноида или группы). Проходя по некоторому пути из начальной вершины в конечную и перемножая последовательно метки рёбер, получаем некоторый элемент моноида (группы), который называется допустимым относительно автомата. Множество всех допустимых элементов называется множеством, допустимым относительно автомата.
Исследования рациональных множеств тесно связаны с изучением конечных автоматов. Известно (см. [17]), что любое допустимое относительно автомата множество является рациональным, и наоборот, любое рациональное множество задаётся конечным автоматом.
Идея использования конечных автоматов актуальна для
теории групп. В классической теории (см.[14], [16]) связь с
группой реализуется с помощью понятия "выбор
порождающих". Эта связь не всегда адекватно отражает то, что
происходит непосредственно в группе. Так в рамках данной
теории определение рационального подмножества группы
зависит от рациональной структуры на группе и не инвариантно
относительно её выбора. Кроме того, оно имеет смысл лишь в
конечно порождённых группах. Тем более естественно изучать
рациональные подмножества групп в смысле
непосредственного определения.
Дальнейшее изучение рациональных множеств в группах проводилось многими авторами (Гилманом [17], Герстеном [16], Шортом [16], Романьковым [20], Баженовой [1]-[3], [10], Недбаем [7]-[9]). Наряду с приведённым выше определением рационального множества использовалось также не равносильное ему понятие /.-рациональности, где L - это рациональный язык, задающий на группе рациональную структуру. В частности, было определено понятие универсальной рациональности и универсальной рациональной структуры на группе. Мы называем рациональную структуру L
на G универсальной, если любое рациональное подмножество R группы G L — рационально. Открытым оказался вопрос существования или отсутствия универсальных рациональных структур для групп из различных классов. В статье [16] Герстеном и Шортом сформулирована проблема о существовании такой рациональной структуры Мна группе Z, в которой М - рациональны все подгруппы группы Z2. Мы называем такую структуру универсальной по подгруппам и естественным образом определяем понятие рационального языка, универсального по подгруппам.
Баженовой Г.А. было доказано (см. [2]), что свободная группа F„ конечного ранга п обладает универсальной рациональной структурой. Также (см. [3]), рациональное подмножество R конечно порожденной группы G L — рационально в какой-нибудь рациональной структуре L тогда и только тогда, когда его дополнение G\R также рационально в G. Группы, в которых дополнения к рациональным подмножествам рациональны, изучались Баженовой Г. А в [1], [3], [10]. Это в точности класс В всех конечно порожденных групп, в которых рациональные подмножества замкнуты относительно всех булевых операций, то есть образуют булеву алгебру.
Класс В содержит все конечно порожденные почти абелевы группы [3] и замкнут относительно операции свободного произведения [1]. Заметим (см. [5]), что подгруппа рациональна в том и только в том случае, если она конечно порождена. Значит, необходимым условием принадлежности группы G классу В является выполнение на G свойства Хаусона, а именно: пересечение конечно порожденных подгрупп группы G должно быть конечно порождено. В целом ряде работ замечено, что свойство Хаусона не выполнено на прямом произведении свободных групп, хотя бы одна из которых неабелева. Значит, класс В не замкнут относительно прямых произведений. Г. А. Баженова доказала в [3], что конечно порожденная нильпотентная группа G принадлежит классу В тогда и только тогда, когда она почти абелева. Она же обобщила это утверждение в [10] на полициклические группы.
В [20] В. А. Романьков установил, что проблема вхождения в L - рациональные подмножества рекурсивно определенной группы G с заданной рациональной структурой L алгоритмически разрешима, и дал подробное описание соответствующего алгоритма. Если рекурсивно определенная группа G допускает универсальную рациональную структуру, то мы получаем таким образом унифицированный алгоритм, решающий проблему вхождения в ее рациональные подмножества.
Там же в [20] доказано, что проблема вхождения в рациональные подмножества произвольной неабелевой свободной нильпотентной группы достаточно большого ранга алгоритмически неразрешима.
Изучение рациональных множеств было продолжено при изучении множеств решений различных систем уравнений. Известно (см. [3]) , что множество неотрицательных решений систем линейных уравнений с целыми коэффициентами рационально.
Решение различных прикладных задач сводится к решению систем линейных уравнений. Многие прикладные задачи, а, следовательно, и их формализация в виде системы линейных уравнений, обладают свойствами симметрии (см. [4]). Симметрия - это ни что иное, как наличие нетривиальной группы автоморфизмов. Поэтому имеет смысл применить методы теории групп для разработки методов решения, менее трудоёмких по сравнению с методами, не учитывающими симметрию.
Основной целью работы является изучение универсальных рациональных множеств в группах.
Научная новизна. Все основные результаты диссертации являются новыми.
В диссертации получены следующие основные результаты:
1) охарактеризованы некоторые свойства универсальной рациональной структуры и универсального рационального языка;
получен ответ на вопрос о существовании универсальных рациональных структур на конечно порождённых группах и универсальной по подгруппам рациональной структуры на свободной абелевой группе Z2 ранга 2;
получены условия эквивалентности бесконечной системы уравнений некоторой своей конечной подсистеме в группе, в общем случае необязательно являющейся эквационально - нетеровой;
разработан метод решения симметричных систем линейных уравнений, позволяющий сократить трудоёмкость решения за счёт использования свойств симметрии этих систем.
Методы исследования опираются на общую и комбинаторную теорию групп, а также теорию конечных автоматов.
Теоретическая и практическая значимость. Основные результаты диссертации носят теоретический характер и могут найти применение в дальнейших исследованиях рациональных подмножеств в группах.
Апробация работы. Результаты диссертации
докладывались на X Всероссийской конференции
"Математическое программирование и приложения" (г.
Екатеринбург, 1997), международной научно-практической
конференции «Современные исследования в астрофизике и
физико-математических науках», (г. Петропавловск, 2004),
международной научной конференции "Теория приближения и
вложения функциональных пространств", (г. Караганда, 2006),
международной научно-практической конференции
"Современные проблемы математики, механики и информационных технологий" (г.Талдыкорган, 2006), Омском алгебраическом семинаре (Омск, 2006).
Публикации. По теме диссертации опубликовано 8 работ ([21] - [28]).
Объём и структура работы. Диссертация состоит из введения и четырёх глав. В работе принята следующая нумерация основных структурных единиц. Все определения и
замечания имеют сквозную нумерацию. Также сквозную нумерацию имеют все теоремы, леммы и следствия полученные нами. Известные результаты, приведённые в работе, имеют двойную нумерацию. Первая цифра - номер главы, вторая -порядковый номер утверждения в главе. Объём работы - 48 страниц. Список литературы включает 28 наименований.
