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

Григоренко, Ольга Викторовна

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

Григоренко, Ольга Викторовна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Омск МЕСТО ЗАЩИТЫ

2005 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

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

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

На правах рукописи

Григоренко Ольга Викторовна оозовтотб

УНИВЕРСАЛЬНЫЕ РАЦИОНАЛЬНЫЕ МНОЖЕСТВА

В ГРУППАХ

01.01.06. - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Омск - 2006

003067076

Работа выполнена на кафедре информационных систем математического факультета ГОУ ВПО "Омский государственный университет им. Ф.М. Достоевского"

Научный руководитель:

доктор физико-математических наук, профессор Романъков Виталий Анатольевич Официальные оппоненты:

доктор физико-математических наук, профессор Мартынов Леонид Матвеевич

кандидат физико-математических наук, Рыболов Александр Николаевич

Ведущая организация:

ГОУ ВПО "Новосибирский государственный технический университет"

Защита состоится

ЭО сре^^з 2003-г в» КОэ на заседании диссертационного совета К 212.179.01 при Омском государственном университете им. Ф.М.Достоевского по адресу: 644077, Омск, пр. Мира, 55А.

С диссертацией можно ознакомиться в библиотеке Омского государственного университета имени Ф.М.Достоевского.

Автореферат разослан Ц & ^екА 2 РО£г

Учёный секретарь диссертационного совета

/Ятт-^ кандидат физ.- мат. наук, доцент (^У^Ц^)___М.А.Шевелин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Изучение конечных автоматов и рациональных (регулярных, распознаваемых) множеств началось в 50-х годах XX века в связи с началом развития вычислительной техники. В настоящее время конечные автоматы применяются при моделировании процессов в различных областях интеллектуальной деятельности человека, например в лингвистике, экономике, философии, биологии. В математике конечные автоматы и рациональные множества -это уже хорошо известные и привычные объекты.

Исследования рациональных подмножеств в группах проводятся в основном методами комбинаторной теории групп. В комбинаторной теории групп основными объектами являются слова в групповом алфавите, отношения эквивалентности между словами, а также свойства слов, инвариантные относительно некоторых преобразований. Комбинаторная теория групп (в отличие от общей теории групп) исследует группы, заданные образующими и определяющими соотношениями. Основы комбинаторной теории групп изложены в классических монографиях Линдона, Шуппа [5] и Магнуса, Карраса, Солитера [6] под общим названием "Комбинаторная теория групп".

Значительная часть проведённых исследований посвящена рациональным языкам (рациональным множествам в свободных моноидах). Здесь можно отметить монографии Гилмана [17], Флойда и Бигеля [15], Харрисона [18], Ревеза [19]. Отметим также фундаментальный труд по автоматным группам Эпстина, Кэннона, Холта, Леви, Патерсона и Терстона [14] и работу по конечным автоматам Эйленберга [13].

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

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

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

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

непосредственного определения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на X Всероссийской конференции "Математическое программирование и приложения" (г. Екатеринбург, 1997), международной научно-практической конференции «Современные исследования в астрофизике и физико-математических науках», (г. Петропавловск, 2004), международной научной конференции "Теория приближения и вложения функциональных пространств", (г. Караганда, 2006), международной научно-практической конференции

"Современные проблемы математики, механики и информационных технологий" (г.Талдыкорган, 2006), Омском алгебраическом семинаре (Омск, 2006).

Публикации. По теме диссертации опубликовано 8 работ ([21] - [28]).

Объём и структура работы. Диссертация состоит из введения и четырёх глав. В работе принята следующая нумерация основных структурных единиц. Все определения и

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

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Определение 1. Пусть М - произвольный моноид. По индукции определим классы Я, , /=0, 1, 2..., подмножеств М следующим образом:

1. Яо- это класс всех конечных подмножеств М.

2. Если классы Ко, Я], ... Я„ уже определены, то определим Яп+х как класс всех множеств 8 с: М таких, что Б не принадлежит ни одному из классов Яо, Яь ... Я„ , но существуют множества 7/ еЯк , Т2еЯ1, 0<к, 1<п, такие, что либо 8=Т^Т2, либо 5=Гу • Т2={аЬ\аеТ1 , ЬеТ2), либо Г^Г/Г;и Т1Т1Т1 и ...

Объединение всех классов Я,, 1=0, 1, 2..., называется классом рациональных подмножеств Ми обозначается ЩМ).

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

Произведение всех меток рёбер, составляющих некоторый путь р в Г, называется меткой пути р. Элемент т еМ называется допустимым автоматом Г, если существует путь с началом в начальной вершине уо и концом в одной из

конечных вершин с меткой т. Множество всех элементов, допустимых автоматом Г, называется множеством, допустимым автоматом Г.

Определение 3. Конечный автомат, из каждой вершины которого выходит ровно одно ребро с каждым порождающим, называется определённым.

Также в этой главе сформулирована теорема, определяющая связь между рациональными множествами и множествами, допустимыми автоматами.

Теорема 1.1. (См. [17]). Класс рациональных над М множеств совпадает с классом множеств, допустима автоматами над М.

Следующие утверждения задают основные свойства рациональных множеств.

Теорема 1.2. (См. [17]). Пусть М и М' - моноиды, ц : М—> М' - гомоморфизм. Тогда:

1. Для любого множества А порождающих М, любое рациональное подмножество М лежит в подмоноиде, порождённом конечным подмножеством А.

2. Рациональные подмножества М замкнуты относительно рациональных операций.

3. Образ любого рационального подмножества М при гомоморфизме ¡л есть рациональное подмножество М'. Если отображение ¡л сюръективно, то каждое рациональное подмножество М' имеет рациональный прообраз в М.

Теорема 1.3. (См.[17]). Пусть £ - произвольный конечный алфавит. Тогда:

1. Рациональный язык над X является прообразом подмножества конечного моноида Р относительно гомоморфизма ¡л : £

2. Класс рациональных языков замкнут относительно булевых операций.

Теорема 1.4. (См. [17]). Любой рациональный язык может быть задан определённым автоматом.

Теорема 1.5. (См. [14]). Пусть G - группа. Подгруппа Н группы G рациональна тогда и только тогда, когда она конечно порождена.

Указан наиболее известный критерий рациональности множества в свободном моноиде (Pumping lemma - Теорема 1.6).

Теорема 1.6. (См. [17]). Пусть М- моноид и R еЩМ). Тогда

1. либо R конечно, либо существуют такие и, v, w из М, что v&l и для всех целых п> 0 элемент uv "w принадлежит R;

2. существуют такие конечные множества Tq.Ti сМ, что 10 Ti и любое г из R\Tо можно представить в виде г = utv так, что teTi и ut*v с R.

Приводится также другое существующие определение рациональности множества, связанное с понятием рациональной структуры.

Определение 4. Пусть G -конечно-порождённая группа, Yr конечный алфавит, £ - свободный моноид, ц : £ G -сюрьективный морфизм моноидов, L - некоторое рациональное подмножество £ и ц( L)= G. Тогда пара CL, у) называется выбором порождающих для G, тройка ц L) называется рациональной структурой на G. Множество RcrG называется ¿-рациональным, если ц (R)r^L рационально. (Это не означает, что выбор порождающих фиксирован; имеется в виду, что "информация о £ и ¡лсодержится в L").

Связь между двумя определениями рациональности даёт следующая

Теорема 1.7. (См. [3]). Рациональное в смысле определения 1 подмножество Я в группе в является Ь-рациональным для некоторого X тогда и только тогда, когда его дополнение Я'=0\Я также рационально в &

Из этой теоремы следует, что существуют подмножества в группах рациональные, но не ¿-рациональные ни для каких рациональных языков Ь, а также множества, являющиеся ¿-рациональным для одного ¿, но не являющегося ¿-рациональным для другого ¿.

В этой связи вводятся определения универсальной структуры и универсального рационального языка.

Определение 5. Рациональная структура д Ьц) называется универсальной, если любое подмножество Я в группе О , являющееся Ь-рациональным в некоторой структуре ¡л, Ь), также является Ьи-рациональным в данной структуре.

Определение 6. Пусть р. : £ —> С гомоморфизм X па конечно- порожденную группу & Язык ¿ с £ назовем /л -универсальным (по подгруппам), или, более просто, универсальным (по подгруппам), если прообраз любого рационального множества (конечно порожденной подгруппы) Я группы й в ¿ рационален.

Далее поясняется суть используемого понятия сложности (высоты) рационального множества.

Вторая глава содержит результаты, касающиеся вопроса о том, когда рациональный язык будет являться универсальным. В первом параграфе второй главы мы доказываем ряд утверждений относительно понятия универсальной рациональной структуры и естественного обобщения этого понятия - //-универсального рационального языка. Эти

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

Лемма 1. Пусть М-рациональный язык, содержащийся в универсальном (по подгруппам) рациональном языке Ь. Тогда М также является универсальным (по подгруппам).

Лемма 2.1) Пусть а - произвольный элемент свободного моноида Тогда язык является рациональным в том

и только в том случае, если рациональны языки аЬ и Ьа.

2) Пусть Ь - произвольный элемент группы & Тогда подмножество Лев рационально в том и только в том случае, если рациональны подмножества ЪК и КЬ.

Лемма 3. Пусть группа такова, что все ее рациональные подмножества образуют булеву алгебру. Тогда в определении ¡л-универсальности языка достаточно

требовать, чтобы были рациональными все прообразы /л^ (/?) рациональных подмножеств образа /л{Ь) языка Ь в группе б.

Здесь ц I означает ограничение /л на Ь. В определении ¡л - универсальности по подгруппам языка достаточно

требовать, чтобы ¡л ь -прообразы пересечений конечно порожденных подгрупп группы О с /л{Ь) были рациональными в

Лемма 4. Пусть конечно порожденная группа О такова, что все ее подмножества образуют булеву алгебру. Тогда рациональный язык Ь универсален в том и только в том случае, если универсальны языки аЬ и Ьа для произвольного

элемента а £ У, *.

Далее введено понятие того, что рациональный язык Z,/ (определенной сложности) существенно используется для построения рационального языка (большей сложности), если существует кратчайшая схема построения языка Ь2 из конечных языков, в которой участвует Lj.

Лемма 5. Пусть конечно порожденная группа G такова, что все ее рациональные подмножества замкнуты по булевым операциям. Пусть язык Ь2 универсален и язык L] существенно использован при построении языка Ь2. тогда язык Lj также универсален.

Лемма 6. Пусть конечно порожденная группа G допускает универсальную структуру L относительно гомоморфизма /л: £ —* G, где £ свободный моноид на конечном

алфавите Пусть имеется другой гомоморфизм V : А* —> G на группу G, где Л ' свободный моноид на конечном алфавите А. Тогда существует универсальная рациональная структура МсЛ*.

Лемма 7. Если существует универсальная рациональная структура для группы G в X. то существует универсальная рациональная структура для G в F.

Лемма 8. Если универсальная рациональная структура для G существует в F, то универсальная рациональная структура для G есть и в £ .

Во втором параграфе второй главы рассмотрены некоторые примеры языков, не являющихся рациональными.

Лемма 9. Пусть элементы и, v €Е таковы, что их образы в Z2 независимы то есть порождают нециклическую

I 100 п П

подгруппу. Тогда язык К = М и V нерационален.

Далее определено понятие линейного и конечно линейного языка и доказана нерациональность ещё одного языка.

Определение 7. Язык L сг£ назовём линейным, если его образ ц (L ) в группе Z2 лежит в смежном классе по какой-нибудь циклической подгруппе группы Z2.

Лемма 10. Пусть Ьг (i = 1,2) - два линейных языка в

образы которых ) бесконечны в Z2 и отвечают

циклическим подгруппам, порожденным независимыми элементами, скажем, cud. Пусть fug соответствующие

представители смежных классов. Обозначим через Lt [и] для

/ = 1,2 подмножества всех элементов в Lh образы которых

равны fc" или gd", соответственно. Тогда для любых k,l G Ыязык

К = [Х_офк]Ь2[п1]

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

Третья глава посвящена изучению вопроса о существовании универсальных рациональных структур на группах. Первый параграф третьей главы содержит доказательство того, что любая конечно порожденная группа G, содержащая в качестве подгруппы свободную абелеву группу Z2 ранга 2, не обладает универсальной рациональной структурой.

Теорема 1. Пусть G конечно порожденная группа, содержащая в качестве подгруппы свободную абелеву группу Z2 ранга 2. Тогда группа G не допускает универсальной рациональной структуры.

Во втором параграфе третьей гдавы мы даём ответ вопрос о существовании такой рациональной, называемой универсальной по подгруппам, структуры М на группе ¿г, в которой М - рациональны все подгруппы группы Полученный результат даёт решение проблемы Герстена-Шорта (см. [16]).

Теорема 2. Группа не допускает рациональной структуры, универсальной по подгруппам.

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

Определение 9. Пусть в - группа, Х],..,Х„-переменные и

групповое слово Ю = g\X*>g2x*21 gn+l) где е,е {±1},

g, еб, /' = 1,..., п. Равенство У1> = 1 называется уравнением в группе в, Кортеж ([¡, /2, ...,/п) элементов группы О называется решением уравнения = 1, если верно равенство

Определение 10. Решением системы № = /:{'и>/ = 1, м>2 =

1, ..., у/т = 1,...} в группе С называется кортеж элементов (/},

/2,...../г,) группы (?, являющийся решением каждого уравнения

системы.

Определение 11. Группа О называется эквационально-нетеровой (или нетеровой по уравнениям), если в ней любая бесконечная система уравнений эквивалентна некоторой своей конечной подсистеме.

Пусть .Рл = X], Х2,.... Хг) - свободная группа, порожденная элементами X] , хг, ..., х„. Пусть в/Зсу, х2 , ..., х„] = -

свободное произведение группы в на Г„ (см. [6]). Тогда групповое слово ту, представляющее левую часть уравнения, может считаться элементом группы С[х1, х2 , ..., Хц}. Все левые части системы уравнений Ж=1 над группой С образуют подмножество в группе С[хи х2, ..., х^.

Определено отображение <р: 0[х\, х2, х^ -> б, полагая:

1 )№еО)(р(!>)=Ш;

2) (Уг) (р (х^ = /ь и это отображение продолжено до гомоморфизма. Тогда, если (/}, /2, . . . - решение уравнения м>

= 1, ф(У9) = 1.

Определение 12. Систему уравнений ¡V = 1 в группе Сг назовем рациональной, если множество левых частей уравнений этой системы является рациональным подмножеством в группе С?/х/, х2, ..., х^.

Теорема 3. Любая рациональная система уравнений в группе С эквивалентна некоторой своей конечной подсистеме.

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

Определение 13. Систему линейных уравнений

<ах >=Ь 1-1,2,..., т, (1)

где а1 =( а\, а\,..., а'п)еИ" назовём симметричной по группе А0,

если множество А-{а1, а2, .... а"1} симметрично по группе Л°, то есть, если А1^={ак\ ае А, А.еЛ°}=Л.

Пусть Л<А°, П - группа, порождённая группой А и множеством А; Рь к=1,2, ...,р- орбиты группы А во множестве {1, 2, ..., и}; ()г, г= 1, 2, ц - орбиты группы П во множестве

{1,2, ..., т}. Полагая^= тт{/{/е Рк}; /к ~ ^ а j(k) ;

«б б,

/'={/{,Я,-,/;); &= Е Ь' \У=(У1> Уз, ...,»>.

>¿0 г

Записана следующая система линейных уравнений:

</',у>=8г,г=1,2,...,д (2)

Теорема 4. Пусть система уравнений (1) имеет * * * *

единственное решение х =( Х\, Х2,..., Х„ ), тогда система

уравнений (2) также имеет единственное решение. При этом * * * *

если у =(У1,У2>'-->УР) -решение системы (2), то

XX = Уь> к = 1,2,...,р. (3)

Теорема 5. Если А- нормальная собственная подгруппа группы Л° и если не существует группы Л1, удовлетворяющей условиям:

1) Л <Л1<Л°;

2) орбиты групп Ли А1 совпадают,

то система (2) симметрична по группе подстановок *Р изоморфной фактор-группе А0/А.

Благодарность. Автор выражает глубокую благодарность научному руководителю профессору Виталию Анатольевичу Романькову за постановку задач, большую поддержку и внимание к работе.

ЛИТЕРАТУРА

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

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

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

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

[5] Линдон Р., Шупп 77. Комбинаторная теория групп. - М.: Мир, 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 K, 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 D.B.A., 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 I I 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 II Международная конференция "Комбинаторные и вычислительные методы в математике". - Омск, 1999. - С.235 - 242.

Публикации автора по теме диссертации

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

[22] Въялицин A.A., Мутанов Г.М., Замиралова O.B. О классификации экстремальных комбинаторных задач // Информационный бюллетень Ассоциации математического программирования.- Екатеринбург: УрО РАН, 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 С.

Подписано в печать 14 12.2006 г. Формат 60x90 1/16. Гарнитура Times. Ризография Объем 0,9 уч.изд.л.; 1,25 усл.печ.л. Тираж 70 экз. Заказ №2453. Бумага книжно-журнальная Отпечатано в Издательско-полиграфическом секторе ИТС Северо-Казахстанского государственного университета им.М.Козыбаева, г.Петропавловск, ул.Пушкина, 81.

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

Введение.

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

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

Идея использования конечных автоматов актуальна для теории групп. Как правило, в рамках этого подхода (см.[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 с заданной рациональной структурой £ алгоритмически разрешима, и дал подробное описание соответствующего алгоритма. Если рекурсивно определенная группа С допускает универсальную рациональную структуру, то мы получаем таким образом унифицированный алгоритм, решающий проблему вхождения в ее рациональные подмножества.

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

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

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

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

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

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

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 С.