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

Введение

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

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

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

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

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

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

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

Глава 4. Полугруппа коцечщи^Д. коконечных подмножеств группы.

§ 4.1. Основные свойства S(GynAutS(G)

§ 4.2. Формульность подмножеств

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

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

Любое рациональное множество задается конечным автоматом. Таким образом, исследование рациональных множеств тесно связано с изучением конечных автоматов.

Вкратце описывая результаты нашего исследования, можно сказать следующее. В этой работе мы доказываем алгоритмическую разрешимость проблемы вхождения в рациональные подмножества для свободных групп и конечно-порожденных абеле-вых групп. Показываем, что разрешимость проблемы вхождения в рациональные подмножества переносится на свободные произведения групп и не переносится на прямые произведения и расширения. Утверждается также, что в группе, содержащей свободную неабелеву подгруппу, существуют рациональные множества любой высоты. Устанавливается рациональность кофинитных множеств для некоторых классов групп (групп с конечным ните-вым базисом, полициклических). Замечено, что рациональности множества G\1 для конечйо-определенной группы G достаточно для разрешимости в G проблемы равенства. Определены некоторые свойства полугруппы S{G) конечных и коконечных подмножеств группы G, а также группы автоморфизмов AutS(G). Введено понятие характеристики элемента из S(G) и доказана формульность классов множеств с одинаковой характеристикой для широкого класса групп.

Скажем теперь несколько слов о разделе алгебры, в котором проводились исследования.

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

Основы комбинаторной теории групп изложены в классических монографиях Линдона, Шуппа [9], и Магнуса, Карраса, Солитера [10] под общим названием "Комбинаторная теория групп".

Возвращаясь к рациональным множествам, мы можем сказать, что они изучаются уже достаточно долго. Правда, основная часть исследований посвящена так называемым рациональным языкам (рациональным множествам в свободных моноидах). Здесь мы можем отметить монографии Гилмана [23], Флойда и Бигеля [20], Харрисона [25], Хопкрофта и Уллмана [27], [28], Гинзбурга [8], Ре-веза [33]. Отметим также фундаментальный труд по автоматным группам Эпстина, Кэннона, Холта, Леви, Патерсона и Терстона [19] и работы по конечным автоматам Эйленберга [17], Голдстай-на [24].

Наши исследования связаны с понятием рационального множества в группе, введенным в рассмотрение Р. Гилманом (см. его обстоятельную обзорную статью [23]).

В этих работах доказаны многие известные результаты о рациональных языках и конечных автоматах. Те из них, которые используются в нашей работе, приведены в Главе 1.

Хотелось бы упомянуть и о более новых исследованиях. Дальнейшее изучение рациональных множеств в группах проведено Г.А. Баженовой и В.А. Романьковым в работах [2], [3], [4], [5], [14], [34]. Опираясь на эти результаты, мы доказываем многие из утверждений в главах 2,3 нашей работы.

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

Первая глава содержит основные определения и известные утверждения, используемые в дальнейшем. В Главе 1 приведены определения рациональных множеств (Определение 1), конечных автоматов (Определение 2) и L-рациональных множеств (Определение 4). Также эта глава включает теорему, определяющую связь между рациональными множествами и множествами допустимыми автоматами (Теорема 1.1). Приведены утверждения, задающие основные свойства рациональных множеств (Теоремы 1.2, 1.3, 1.4, 1.5). Указан наиболее известный критерий рациональности множества в свободном моноиде (Pumping lemma - Теорема 1.6). В Главу 1 включены также утверждения (Теоремы 1.7, 1.8, 1.9), используемые нами при доказательстве некоторых результатов в главах 2,3. На основании этих утверждений мы вводим альтернативное определение Х-рационального множества в группе (Определение 6), с помощью которого получается простое доказательство известной теоремы из [23] о "Word Problem" (Теорема 1.10).

В Главе 2 рассматриваются алгоритмические вопросы. Естественным образом возникает вопрос определения для произвольного элемента д G G принадлежности к заданному рациональному множеству R, то есть - проблема вхождения в рациональные подмножества. Заметим, что под заданием множества R понимается определение схемы получения этого рационального множества из конечных подмножеств рациональными операциями. Как показано в работе [34], для свободных нильпотентных групп ступени > 2 и достаточно большого ранга, проблема вхождения в рациональные подмножества неразрешима.

Рассмотрим в качестве группы G свободную абелеву группу G = Zn. В работе [13] А.В. Нечайкиным доказана разрешимость проблемы вхождения в рациональные подмножества для этой группы при наличии некоторых дополнительных условий (заданной структуре рационального множества). Мы доказываем алгоритмическую разрешимость этой проблемы в общем случае (Предложение 1). Отсюда получается разрешимость проблемы вхождения в рациональные множества для произвольной конечно порожденной абелевой группы (Теорема 2). В этом же параграфе мы приводим доказательство алгоритмической разрешимости проблемы вхождения в рациональные подмножества для свободной группы (Теорема 1). Доказано существование алгоритма построения по автомату для рационального множества R автомата для его дополнения в свободном моноиде (Теорема 2.1). Также показано существование алгоритма построения автомата для пересечения рациональных множеств в свободном моноиде.

В следующем параграфе Главы 2 мы доказываем, что если в группах G и Н разрешима проблема вхождения в рациональные подмножества, то она разрешима и в их свободном произведении (Теорема 3). Г.А. Баженовой в работе [2] была доказана похожая теорема, в которой утверждалось, что если в(?иЯ рациональные множества образуют булеву алгебру, то они образуют булеву алгебру ив G* Н. Для нашего утверждения требуется более слабое условие на группы G и Н. А именно, достаточно рекурсивной перечислимости рационального множества и его дополнения. Оказалось, что используя построенные в доказательстве основной теоремы работы [2] множества, можно доказать разрешимость проблемы вхождения в рациональные подмножества свободного произведения групп. Далее в этом параграфе, опираясь на результаты работ [10], [12], [34], мы замечаем также, что разрешимость проблемы вхождения в рациональные подмножества не переносится на прямые произведения и расширения групп.

В Главе 3 мы рассматриваем понятие высоты рационального множества. Высота рационального множества - это характеристика его сложности. Пином в работе [30] рассматриваются различные иерархии рациональных множеств в моноидах. Однако, нетрудно заметить, что многие из них вырождаются в групповом случае. В нашей работе мы используем приведенное ниже определение высоты (сложности).

Высота рационального множества определяется следующим образом. Высота конечного множества равна 0. Рациональное подмножество R группы G имеет высоту п, если оно предста-вимо в виде R = (J-Ц 9пЩ^2. Щдц.+1, где g{j е G, K{j С G и Kij - рациональные множества высоты < п — 1 в G, и Л не представимо в таком виде для К^ высоты < п — 1.

Изучение вопроса высоты рационального множества возникло при рассмотрении результатов работы [18], в которой показано, что рациональные множества в свободной абелевой группе можно представить в виде конечного объединения сдвигов свободных коммутативных моноидов. Таким образом, в свободной абелевой группе рациональные множества имеют высоту 0 или 1.

Приведенное понятие высоты рационального множества было введено М. Шутзенбергером и Ф. Деджином в [16]. В этой же работе было показано существование рациональных множеств произвольной высоты в свободном моноиде {а, &}*. Опираясь на этот результат, Р. Томас и Т. Хербст в [26] доказали существование рациональных множеств высоты 2 в свободной группе ранга 2. Нам удалось обобщить этот результат, доказав, что произвольная группа, содержащая свободную неабелеву подгруппу, содержит рациональные подмножества любой наперед заданной высоты (Теорема 5).

Продолжая исследования алгоритмических вопросов, в частности, проблемы равенства, мы пришли к рассмотрению кофинитных подмножеств группы. Здесь нам удалось установить, что рациональности кофинитных подмножеств конечно-определенной группы G, даже рациональности G\ 1, достаточно для разрешимости в G проблемы равенства (Теорема 6).

Было также замечено, что в группах с конечным нитевым базисом и единственностью записи по этому базису кофинитные подмножества рациональны (Теорема 7).

Исследование рациональности кофинитных подмножеств в Главе 3 оказалось тесно связанным со свойствами полугруппы S(G) конечных и коконечных подмножеств группы G. Именно эта полугруппа и рассматривается в Главе 4. Мы изучаем некоторые свойства полугруппы S(G) (в основном для группы G без кручения) (Теорема 8). Мы вводим понятие характеристики коконечного элемента из S(G) (Определения 10, 11, 12) и доказываем формульность подмножеств с одинаковой характеристикой (Леммы 2, 3, Теорема 10). Отсюда следует как формульность в S(G) множества всех множеств одного конечного порядка, так и формульность множества всех их дополнений в S(G). Кроме этого мы выявляем ряд свойств группы автоморфизмов AutS(G) (Теорема 9, Пример 1, Предложение 7).

О некоторых результатах диссертации сообщалось на международном семинаре по теории групп, проходившем с 17 по 21 декабря 2001 года в Екатеринбурге.

Результаты диссертации докладывались и обсуждались на алгебраическом семинаре ОмГУ, научных конференциях студентов и аспирантов ОмГУ.

Основные результаты диссертации опубликованы в работах [36],[37],[38],[39],[40],[41],[42].

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

1. Анисимов А.В., Групповые языки// Кибернетика, №4, 1971, С.594-601.

2. Баженова Г.А., Замкнутость одного класса групп относительно свободного произведения// Сибирский математический журнал, 41, №4, 2000, С.740-743.

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

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

5. Баженова Г.А., О рациональных множествах в метабелевых группах// Препринт №22. Омск: ОмГАУ, 1999, 4с.

6. Блудов В.В., О нитевых базисах в группах// Третья международная конференция по алгебре памяти М.И.Каргаполова: Тез.докл. Красноярск: ИНОПРОФ, 1993, С.43-44.

7. Ван-дер-Варден Б.Л., Алгебра// М.: Наука, 1976, 648с.

8. Гинзбург С., Математическая теория контекстно-свободных языков// М.: Мир, 1970.

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

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

11. Мальцев А.И., Алгоритмы и рекурсивные функции // М.: Наука, 1986, 368с.

12. Михайлова К.А., Проблема вхождения для прямого произведения групп // Математический сборник 70(112), 1966, С.241-251.

13. Нечайкин А.В., О решении уравнений над абелевыми группами // Дипломная работа. ОмГУ, 1999.

14. Bazhenova G.A., Rational sets in polycyclic groups // В сб.: B.A. Романьков ред., Комбинаторные и вычислительные методы в математике, Омск: ОмГУ, 1999, С.76-81.

15. Brzozowski J.A., Open problems about regular languages// In: R. V.Book, ed., Formal Language Theory Perspectives and Open Problems ,Academic Press, New York, 1980, P.23-47.

16. F.Dejean and M.P.Schiitzenberger, On a question of Egganf / Inform, and Control, 9, 1966, P.23-25.

17. Eilenberg S., Automata, Languages and Machines, A and B// Academic Press, New York, 1974.

18. Eilenberg S., Schutzenberger M.P., Rational sets in commutative monoids// J. Algebra 13, 1969, P.173-191.

19. Epstein D.B., Cannon J.W., Holt D.F., Levy S.V., Paterson M.S., Thurston W.P., Word Processing in Groups// Jones and Bartlett, Boston, 1992.

20. Floyd R., Biegel R., The Language of Machines// Computer Press, New York, 1994.

21. Gersten S.M., Short H., Rational subgroups of biautomatic groups// Annals of Math, 134, 1992, P.125-158.

22. Gersten S.M., Introduction to hyperbolic and automatic groups// Mathematics Department, University of Utah, Salt Lake City, UT84112, USA, 1996, 26P.

23. Gilman R.H., Formal Languages and Infinite Groups// DIMACS Series in Discrete Mathematics and Theoretical Computer Science. P.27-51.

24. Goldstine J., Formal languages and their relation to automata: What Hopcroft & Ullman didn't tell us// In: R.V.Book, ed., Formal Language Theory Perspectives and Open Problems, Academic Press, New York, 1980, P.109-140.

25. Harrison H., Introduction to Formal Language Theory// Addison-Wesley, Reading, MA., 1978.

26. Herbst Т., Thomas R.M., Group presentations, formal languages and characterizations of one-counter groups// Theoretical Computer Science, 112, 1993, P.187-213.

27. Hopcroft J.E., Ullman J.D., Formal languages and their relation to automata// Addison-Wesley, Reading, MA., 1969.

28. Hopcroft J.E., Ullman J.D., Introduction to Automata Theory, Languages and Computation// Addison-Wesley, Reading, MA., 1979.

29. Pin J.E., Semigroupe des parties et relations de Green// Can. J. Math, 1984, 36, №2, P.323-343.

30. Pin J.E., Polynomial closure of group languages and open sets of the Hall topology// Theoretical Computer Science, 169, 1996, P. 185-200.

31. Pin J.E., Straubing H., Therien D., New results on the generalized star-height problem// In: B.Monien and R.cori, eds., Proc. STACS'89, Lecture Notes in Computer Science, vol.349, Springer, Berlin, 1989, P.458-467.

32. Putcha Mohan S., Subgroups of the power semigroup of a finite semigroup// Can. J. Math, 1979, 31, №5, P.1077-1083.

33. Revesz G., Introduction to Formal Languages// McGraw Hill, 1983.

34. Roman'kov V.A., On the occurence problem for rational subsets of a group/J В сб.: В.А. Романьков ред., Комбинаторные и вычислительные методы в математике. Омск: ОмГУ, 1999, С.235-242.

35. Short Н., Groups and normal forms // The City College of New York, 1993, 22P.Публикации по теме диссертации:

36. Недбай М.Ю., Проблема вхождения в рациональные подмножества конечно порожденных абелевых групп// Вестник Омского университета,. №3, 1999, С.37-40.

37. Недбай М.Ю., Проблема вхождения в рациональное подмножество свободного произведения групп// Вестник Омского университета, №2, 2000, С.17-18.

38. Недбай М.Ю., Романьков В.А, Свойства полугруппы конечных и коконечных подмножеств бесконечной группы// В сб. Сборник трудов международного семинара по теории групп. Екатеринбург. Россия. 17-21 декабря 2001г.

39. Недбай М.Ю., 0 высоте рациональных подмножеств в группах // Вестник Омского университета, №4, 2001, С.11-13.

40. Недбай М.Ю., 0 рациональности кофинитных подмножеств в группах // Вестник Омского университета, №4, 2001, С.19-21.

41. Недбай М.Ю., Некоторые свойства рациональных множеств в группах // В сб. Тезисы международного семинара по теории групп. Екатеринбург. Россия. 17-21 декабря 2001г., С.158-160.

42. Недбай М.Ю., Романьков В.А, Свойства полугруппы конечных и коконечных подмножеств бесконечной группы // В сб. Тезисы международного семинара по теории групп. Екатеринбург. Россия. 17-21 декабря 2001г., С.161-164.