Универсальные рациональные множества в группах тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Григоренко, Ольга Викторовна

• Григоренко, Ольга Викторовна
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Григоренко, Ольга Викторовна

Введение.

Глава 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].

Класс рациональных (регулярных, распознаваемых) подмножеств произвольного моноида М классически определяется как минимальный класс, содержащий все конечные подмножества М и замкнутый относительно рациональных операций, то есть объединения, умножения и порождения подмоноида. Взяв в качестве моноида М группу С, получаем определение рациональных подмножеств в группе (7.

Конечный автомат - это конечный ориентированный граф, в котором выделена некоторая вершина, называемая начальной, и подмножество вершин, называемых конечными (или допустимыми). Рёбра графа имеют метки - элементы некоторого множества (моноида или группы). Проходя по некоторому пути из начальной вершины в конечную и перемножая последовательно метки рёбер, получаем некоторый элемент моноида (группы), который называется допустимым относительно автомата. Множество всех допустимых элементов называется множеством, допустимым относительно автомата.

Исследования рациональных множеств тесно связаны с изучением конечных автоматов. Известно (см. [17]), что любое допустимое относительно автомата множество является рациональным, и наоборот, любое рациональное множество задаётся конечным автоматом.

Идея использования конечных автоматов актуальна для теории групп. Как правило, в рамках этого подхода (см.[14], [16]) рассматриваются рациональные подмножества свободных моноидов, а связь с группой реализуется с помощью понятия "выбор порождающих". Эта связь не всегда адекватно отражает то, что происходит непосредственно в группе. Так в рамках данной теории определение рационального подмножества группы зависит от рациональной структуры на группе и не инвариантно относительно её выбора. Кроме того, оно имеет смысл лишь в конечно порождённых группах. Тем более естественно изучать рациональные подмножества групп в смысле непосредственного определения.

Дальнейшее изучение рациональных множеств в группах проводилось В.А. Романьковым и его учениками Г.А. Баженовой, М.Ю. Недбаем (см. [1] -[3]> [7]-[9], [Ю], [20]). В этих работах использовалось определение рациональных множеств через рациональные операции, а также не равносильное ему понятие ¿-рациональности, где Ь - это рациональный язык, задающий на группе рациональную структуру. В частности, было определено понятие универсальной рациональности и универсальной рациональной структуры на группе.

Мы называем рациональную структуру Ь на б универсальной, если любое рациональное подмножество Я группы (7 £ - рационально. Открытым оказался вопрос существования или отсутствия универсальных рациональных структур для групп из различных классов. В статье [16] Герстеном и Шортом сформулирована проблема о существовании такой рациональной структуры М на группе 2, в которой М - рациональны все подгруппы группы 22. Мы называем такую структуру универсальной по подгруппам и естественным образом определяем понятие рационального языка, универсального по подгруппам.

Г.А Баженовой, было доказано (см. [2]), что свободная группа /•*„ конечного ранга п обладает универсальной рациональной структурой. Также ею установлено (см. [3]), что рациональное подмножество /? конечно порожденной группы О Ь - рационально в какой-нибудь рациональной структуре Ь тогда и только тогда, когда его дополнение О\Я также рационально в С. Группы, в которых дополнения к рациональным подмножествам рациональны, изучались Г. А. Баженовой в [1], [3], [10]. Это в точности класс И всех конечно порожденных групп, в которых рациональные подмножества замкнуты относительно всех булевых операций, то есть образуют булеву алгебру.

Класс И содержит все конечно порожденные почти абелевы группы [3] и замкнут относительно операции свободного произведения [I]. Заметим (см. [5]), что подгруппа рациональна в том и только в том случае, если она конечно порождена. Значит, необходимым условием принадлежности группы (7 классу Д является выполнение на С свойства Хаусона, а именно: пересечение конечно порожденных подгрупп группы (7 должно быть конечно порождено. В целом ряде работ замечено, что свойство Хаусона не выполнено на прямом произведении свободных групп, хотя бы одна из которых неабелева. Значит, класс /? не замкнут относительно прямых произведений. Г. А. Баженова доказала в [3], что конечно порожденная нильпотентная группа С принадлежит классу й тогда и только тогда, когда она почти абелева. Она же обобщила это утверждение в [10] на полициклические группы.

В [20] В. А. Романьков установил, что проблема вхождения в Ь -рациональные подмножества рекурсивно определенной группы (7 с заданной рациональной структурой £ алгоритмически разрешима, и дал подробное описание соответствующего алгоритма. Если рекурсивно определенная группа С допускает универсальную рациональную структуру, то мы получаем таким образом унифицированный алгоритм, решающий проблему вхождения в ее рациональные подмножества.

Там же в [20] доказано, что проблема вхождения в рациональные подмножества произвольной неабелевой свободной нильпотентной группы достаточно большого ранга алгоритмически неразрешима.

Изучение рациональных множеств было продолжено при изучении множеств решений различных систем уравнений. Известно (см. [3]) , что множество неотрицательных решений систем линейных уравнений с целыми коэффициентами рационально.

Решение различных прикладных задач сводится к решению систем линейных уравнений. Многие прикладные задачи, а, следовательно, и их формализация в виде системы линейных уравнений, обладают свойствами симметрии (см. [4]). Симметрия - это ни что иное, как наличие нетривиальной группы автоморфизмов. Поэтому имеет смысл применить методы теории групп для разработки методов решения, менее трудоёмких по сравнению с методами, не учитывающими симметрию.

Основной целью работы является изучение универсальных рациональных множеств в группах.

Научная новизна. Все основные результаты диссертации являются новыми.

В диссертации получены следующие основные результаты:

1) охарактеризованы некоторые свойства универсальной рациональной структуры и универсального рационального языка;

2) получен ответ на вопрос о существовании универсальных рациональных структур на конечно порождённых группах и универсальной по подгруппам рациональной структуры на свободной абелевой группе / ранга 2;

3) получены условия эквивалентности бесконечной системы уравнений некоторой своей конечной подсистеме в группе, в общем случае необязательно являющейся эквационально - нетеровой;

4) разработан метод решения симметричных систем линейных уравнений, позволяющий сократить трудоёмкость решения за счёт использования свойств симметрии этих систем.

Методы исследования опираются на общую и комбинаторную теорию групп, а также теорию конечных автоматов.

Теоретическая и практическая значимость. Основные результаты диссертации носят теоретический характер и могут найти применение в дальнейших исследованиях рациональных подмножеств в группах.

Структура работы. Диссертация состоит из введения и четырёх глав. В работе принята следующая нумерация основных структурных единиц. Все определения и замечания имеют сквозную нумерацию. Также сквозную нумерацию имеют все теоремы, леммы и следствия полученные нами. Известные результаты, приведённые в работе, имеют двойную нумерацию. Первая цифра - номер главы, вторая - порядковый номер утверждения в главе.

Список литературы диссертационного исследования кандидат физико-математических наук Григоренко, Ольга Викторовна, 2005 год

1. Баженова Г.А. Об одном классе групп, замкнутых относительно свободных произведений // Сиб. мат. ж. - 2000. - Т.4. - №41. - С. 740 -743.

2. Баженова Г. А. Кандидатская диссертация. Омск: ОмГУ, 1999.

3. Баженова Г. А . О рациональных множествах в конечно порожденных нильпотентных группах // Алгебра и логика.- 2000.-Т.4.- №39. -С.397 -394.

4. Вьяпицин А А. Симметричные многогранные множества двойственных задач линейного программирования // Ин-т матем. и механ. Уро АН СССР. Деп. В ВИНИТИ №8445-В88.

5. Линдон Р. Шупп П. Комбинаторная теория групп. М.: Мир, 1980.

6. Магнус В., Каррас Л. Солитер Д. Комбинаторная теория групп. М.: Наука, 1974.

7. Недбай М.Ю. Кандидатская диссертация.- Омск: ОмГУ, 2002.

8. Недбай М.Ю. Некоторые свойства рациональных множеств в группах // Международный семинар по теории групп. Екатеринбург, 2001.-С.158-160.

9. Недбай М.Ю. О высоте рациональных подмножеств в группах // Вестник Омского университета.- Омск: Изд-во ОмГУ, 2000,- Вып.4 -С.11-13.

10. Bazhenova G. A. Rational sets in polycyclic groups // Международная конференция "Комбинаторные и вычислительные методы в математике". Омск, 1999. - С. 76 - 81.

11. Baumslag G. Myasnikov A., Roman'kov V. Two theorems about Equationally Noetherian Groups // Journal of Algebra. 1997.- V 194.- P. 654-664.

12. Dejean F., Thomas R.M. Group presentations, formal languages and characterizations of one-counter groups // Theoretical Computer Science. -1993.-V 112. P.187-213.

13. Eilenberg S. Automata, Languages, and Machines, A and B. New York : Academic Press, 1974.

14. Epstein DBA. Cannon J.V. Holt D.F. Levy S.V.F., Paterson M.S. Thurston W.P. Word processing in groups. Boston - London: Jones and Bartlett, 1992.

15. Floyd R. Biegel R. The Language of Machines. New York: Computer Press, 1994.

16. Gersten S.M., Short H.B. Rational subgroups of biautomatic groups // Annals of Mathematics. 1992.- V 134.- P. 125-158.

17. Gilman R.H. Formal Languages and Infinite Groups // DIMACS Series in Discrete Mathematics and Theoretical computer science, AMS. 1996.- V. 25-P. 27-51.

18. Harrison H. Introduction to Formal Language Theory Addison-Wesley Reading, MA., 1979.

19. Revesz G. Introduction to Formal Languages. McGraw Hill, 1983.

20. Roman'kov V. A. On the occurrence problem for rational subsets of group I/ Международная конференция "Комбинаторные и вычислительные методы в математике". Омск, 1999. - С.235-242.Публикации автора по теме диссертации

21. Вьялицин А.А., Замиралова О.В. Симметричные системы линейных уравнений // Вестник Северо-Казахстанского университета. — Петропавловск, Изд.-во СКУ, 1997.-№2. С. 17-21.

22. Вьялицин А.А., Мутанов Г.М. Замиралова О.В. О классификации экстремальных комбинаторных задач // Информационный бюллетень Ассоциации математического программирования.- Екатеринбург: УрО РАН, 1997.-№7,- С.59-60.

23. Григоренко О.В. Об универсальных рациональных языках относительно данной группы // Вестник Омского университета.- Омск: Изд-во ОмГУ, 2005,- Вып.4,- С.21-23.

24. Григоренко О.В. О рациональных системах уравнений в группах // Вестник Омского университета.- Омск: Изд-во ОмГУ, 2003.- Вып.4.-С.15 -16.

25. Григоренко О.В. К вопросу об универсальности рационального языка // Международная научно-практическая конференция "Современные исследования в астрофизике и физико-математических науках".-Петропавловск, 2004,- С.82 84.

26. Григоренко О.В. К вопросу о существовании универсальных рациональных структур на группах // Международная научная конференция "Теория приближения и вложения функциональных пространств".-Караганда, 2006.

27. Григоренко О.В., Романьков В.А. О существовании универсальных рациональных структур на группах // Международная научно-практическая конференция "Современные проблемы математики, механики и информационных технологий". Талдыкорган, 2006.

28. Григоренко О.В., Романьков В.А. Универсальные рациональные структуры на группах: Препринт №.06-01 Петропавловск: Изд-во СКГУ, 2006.-19 С.