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

• Баженова, Галина Александровна
• кандидат физико-математических наук
• 2000

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

Введение

Содержание диссертации 13 I Основы теории рациональных множеств в группах

1 Основные определения

2 Связь двух определений рациональности

3 Множества решений уравнений в к. п. нильпотентных группах

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

4 Абелевы группы

5 Полициклические группы

6 Метабелевы группы

III О классе групп, рациональные подмножества которых — булевы алгебры

7 Свободные произведения

IV О разрешимых группах типа FP

8 О почти абелевости некоторых разрешимых групп типа

Введение диссертации (часть автореферата) на тему «О рациональных множествах в разрешимых группах»

Изучение конечных автоматов и рациональных (регулярных, распознаваемых) множеств началось в 50-х годах XX века в работах [1], [2], [3], [4]. Стимулом и своеобразным "социальным заказом" послужило начало развития вычислительной техники. Понятие конечного автомата близко также таким областям интеллектуальной деятельности, как лингвистика, философия, биология (в которых они часто используются для моделирования). Для математики в данный момент конечные автоматы и рациональные множества — это хорошо известные и привычные объекты теории полугрупп (также хорошо известна параллель между этими объектами, которая устанавливается классической теоремой Клини) — см., например, монографии [5], [6], [7]. Однако классическая теория полугрупп ограничивается изучением рациональных множеств и конечных автоматов в свободных моноидах, хотя определения этих понятий естественно переносятся на случай произвольного моноида (в частности, группы). Идея использования конечных автоматов (причем в разных пониманиях) в данный момент актуальна для теории групп, и работы, связанные с этой тематикой, вызывают большой интерес. Например, известны понятия рациональной структуры, автоматной и биавтоматной структур, комбингов ("причесываний") на группе и др.; возникла новая содержательная теория — см., например, [8], [9], [10]. Однако в рамках этого подхода также рассматриваются лишь рациональные подмножества свободных моноидов, а связь с группой реализуется с помощью понятия "выбор порождающих". Эта связь, на наш взгляд, не всегда адекватно отражает то, что происходит непосредственно в группе. Например, в рамках данной теории определение рационального подмножества группы зависит от рациональной структуры на группе и не инвариантно относительно ее выбора. Кроме того, оно имеет смысл лишь в конечно порожденных группах. Тем более естественно изучать рациональные подмножества групп в смысле непосредственного определения. В этой области лучше всего изучены свободные группы. Отметим, например, такие работы, как [11], [12], [13]. Данная диссертация также следует этому подходу. Однако в ней более подробно изучаются не свободные группы, а разрешимые.

Вначале расскажем более подробно о том, что такое конечные автоматы. Пусть задан некоторый конечный алфавит А (то есть просто некоторое конечное множество). Его элементы будем называть буквами и обозначать символами а,Ь,с. Словом алфавита А будем называть произвольную конечную последовательность ai • ■ • ап букв из алфавита А. В частности, словом является (единственная) пустая последовательность, которую обычно обозначают е. Множество всех слов алфавита А обозначается А*. Число п — это длина слова Oi • • -ап, длина пустого слова — нулевая. Длина слова w Е А* обычно обозначается |ги|. На множестве А* х А* пар слов из А* определена операция конкатенации, или "склеивания": из двух слов w = Gi • • • ап, v = bi • • • bm она конструирует новое слово wv = ai • • • anbi ■ ■ -bm длины m + n = |ги| + Ясно, что эта операция ассоциативна, и слово нулевой длины е является единицей относительно этой операции: для любого w £ А* имеем we = ew = w. Это означает, что множество А* относительно операции конкатенации является моноидом. В действительности моноид А* является свободным: если задан другой моноид М (т.е. множество с определенной на нем бинарной операцией, которая ассоциативна и обладает единицей), то любое отображение / : А -4 М (единственным образом) продолжается до морфизма / : А* —у М, то есть до отображения, "сохраняющего операцию": f(wv) = f(w)f(v), и /(е) = 1. (Способ продолжения при этом очевиден: f(ax---an) = /(ai) • • ■ f(an), если аг- принадлежат А. Также очевидно, что так определенное отображение будет "сохраняющим операцию". Содержательной частью утверждения здесь является то, что данное определение не приводит к противоречиям — ведь слово из А* записывается как произведение букв единственным образом. Это и есть "свобода" А*.) Любое подмножество Ь С А* называется языком над алфавитом А. Можно рассматривать данное понятие языка как некоторую модель "естественного" языка (например, русского или английского). Конечно, аналогия получается довольно грубая, потому что границы естественного языка всегда несколько расплывчаты — например, по поводу принадлежности некоторых высказываний к языку носители языка могут расходиться во мнениях, кроме того, не совсем ясно, что считать "словом" — ведь нельзя понимать русский язык просто как набор слов, "минимальной смысловой единицей" должно быть по меньшей мере предложение. Однако для искусственного и строго формализованного языка (например, языки программирования) модель получается вполне адекватной.

Если мы рассматриваем языки как подмножества свободных моноидов, то сразу же приходится накладывать определенные ограничения, иначе никакой содержательной информации о них получить не удастся. Эти ограничения должны состоять в требовании от языков некоторой степени "разумности", и, по-разному формализуя это понятие, получим различные классы языков, с которыми можно разумно работать. Например, можно потребовать, чтобы принадлежность слова к языку можно было проверять некоторым механическим способом. С другой стороны, можно потребовать, чтобы существовал некоторый механический способ генерирования всех элементов данного языка. Например, можно изучать рекурсивные или рекурсивно перечислимые языки — для первых существуют машины Тьюринга, эффективно проверяющие принадлежность слова к данному языку, для вторых существует алгоритм (реализуемый с помощью машин Тьюринга), выдающий по очереди все слова из данного языка. Аналогично, рациональные языки — это в точности языки, связанные с конечными автоматами, причем можно понимать это и в том смысле, что конечный автомат проверяет принадлежность слова к данному языку, и в том смысле, что конечный автомат генерирует все слова из данного языка. Рассмотрим следующий пример конечного автомата:

Здесь окружности — это вершины или, по-другому, состояния автомата, линии, соединяющие вершины — это ребра или стрелки (они имеют направление, и это тоже отражено на рисунке). Ребра имеют метки — это буквы, скажем, алфавита А. Две вершины на данном рисунке играют особую роль. Они помечены, соответственно, входящей стрелкой, у которой нет начала, и выходящей стрелкой, которая не ведет ни в какую вершину. Первая вершина называется начальной, вторая — выходной. У всякого конечного автомата должна быть единственная начальная вершина и по крайней мере одна выходная. Конечный автомат генерирует множество слов следующим образом. В нем есть пути — например, путь 2 — 3 — 3 — 3 — 4 (здесь числа — это номера вершин). По пути определяется его метка, которая является последовательностью меток тех ребер, из которых этот путь состоит — для данного пути это ЬссЬ. Теперь будем рассматривать только те пути, которые начинаются Ь в первой (т.е. начальной) вершине и заканчиваются в четвертой (выходной). Множество их меток — это и есть множество слов, которое генерируется данным автоматом.

С другой стороны, заметим, что в данном автомате из каждой вершины выходит не более одной стрелки с каждой меткой (такой конечный автомат называется детерминированным). Поэтому для каждого слова ю (например, для слова ю = аЬсЬ) существует не более одного пути из начальной вершины с меткой го. (Ясно, что для гу = аЬсЬ из вершины номер 1 путь должен вести в вершину номер 2, иначе первая буква его метки будет не а, далее в вершину номер 3, потом снова в вершину номер 3 и, наконец, в вершину номер 4.) При такой попытке восстановить путь по слову есть три возможности — либо получен путь с данной меткой из начальной вершины в выходную (пример — слово аЬсЬ), либо получен путь с данной меткой из начальной вершины в вершину, которая выходной не является (пример — слово Ьссс), либо процесс оборвался на том, что из какой-то вершины просто нет стрелок с нужной меткой (пример — слово ааЬ). Но ясно, что в первом случае явным образом получено доказательство того, что данное слово принадлежит языку, заданному этим автоматом, а в последних двух случаях наша неудача означает, что данное слово не может принадлежать этому языку. Таким образом, детерминированный конечный автомат можно понимать также как машину, которая проверяет принадлежность слова некоторому языку. Но, как показано, например, в [8], любой язык, заданный конечным автоматом, задан и некоторым детерминированным конечным автоматом. Значит, можно понимать связь между языком и автоматом и в этом смысле.

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

Итак, рациональные языки можно задавать с помощью конечных автоматов. Существуют и другие способы их определения. Известно, например, что любой рациональный язык можно задать с помощью так называемого рационального выражения. Например, язык, который задан изображенным выше автоматом, можно записать с помощью рационального выражения аЬс*Ь + Ьс*Ь. Здесь сумма означает объединение множеств, звездочка — порождение множеством подмоноида. Вообще класс рациональных подмножеств свободного моноида А* можно определить как замыкание класса всех его конечных подмножеств относительно операций объединения, произведения двух множеств и порождения множеством подмоноида. То, как рациональное множество получается из конечных с помощью указанных операций, и отражает рациональное выражение — конечные множества записываются просто как суммы слов, произведение множеств соответствует приписыванию к одному рациональному выражению другого, объединение соответствует сумме, "навешивание" звездочки — это порождение моноида. В конечных автоматах, соответственно, параллельное соединение двух составных частей эквивалентно объединению, последовательное — произведению, "зацикливание" (петли) дает порождение подмоноида. Отсюда интуитивно понятно, почему рациональные выражения и конечные автоматы порождают один и тот же класс языков.

Если вместо свободного моноида А* взять произвольный моноид М (например, группу), то определить рациональные множества (в общем случае мы говорим "множества", а не "языки") можно полностью аналогично — как порожденные конечными автоматами с метками из М, а также как замыкание класса конечных подмножеств относительно объединения, произведения и порождения подмоноида. Разница в том, что теперь конечный автомат уже нельзя понимать как машину, которая эффективно вычисляет, принадлежит ли элемент данному множеству или нет. Более того, в общем случае такой машины может и не существовать, даже если рассматривать максимально широкий класс машин — машины Тьюринга (см., например, [19]). Заметим, что в общем случае любое рациональное подмножество М может быть получено как гомоморфный образ некоторого рационального подмножества конечно порожденного свободного моноида.

С другой стороны, так как любой конечно порожденный моноид М является гомоморфным образом конечно порожденного свободного моноида А*, то можно характеризовать подмножества 5 С М их прообразами из А* или пересечениями этих прообразов с некоторым языком Ь С А*, в частности, рациональность Б определять как рациональность прообраза. Известен такой вопрос: пусть Ь С А* — полный прообраз единицы при некотором морфизме / : А* —» С, где С — группа. Язык Ь называют проблемой равенства слов. Задача состоит в том, чтобы описать все группы б, у которых проблема равенства слов принадлежит к определенному классу формальных языков. Например, известно, что рациональной проблемой равенства слов обладают конечные группы и только они. У свободных групп конечного ранга проблема равенства слов — контекстно-свободный язык. Можно поставить вопрос иначе: если группа задана с помощью конечного множества порождающих и множества определяющих соотношений Я из некоторого класса формальных языков, что можно сказать об этой группе? Легко доказать, что если Я рационально, то группа конечно определена. В действительности верно большее: если Я контекстно-свободное, то группа конечно определена. Можно заметить, что требование, чтобы проблема равенства была "хорошей" или существовал "хороший" набор определяющих соотношений — это некоторое условие на "ядро" данного представления, на то, что "сокращается". Можно подойти с другой стороны и задавать некоторые требования хороших алгоритмических свойств "того, что остается" . Можно, например, выбрать в А* некоторое (скажем, рациональное) множество Ь представителей всех элементов данной группы и спросить, нельзя ли построить машину, которая бы по слову т е Ь находила представитель V из Ь для его произведения на некоторый фиксированный порождающий. Если ограничить себя условием, что эта машина должна быть некоторым конечным автоматом "от двух переменных", то получается понятие автоматной группы (более точно см. в [8]). Более широкий класс групп, соответствующий более широкому классу машин, — асинхронно автоматные группы. Изучается также класс биавтоматных групп, который содержится в классе автоматных, но неизвестно, совпадают ли они. Автоматные группы обладают рядом полезных свойств, например, они являются конечно определенными и удовлетворяют квадратичному изопериметрическому неравенству, то есть, если задано некоторое представление автоматной группы, то любой элемент свободной группы V), представляющий единицу, может быть записан как произведение не более чем С|ги|2 сопряженных с соотношениями и их обратными, где С не зависит от выбора го. В биавтоматной группе разрешима проблема сопряженности, то есть существует машина Тьюринга, которая, получая на входе два слова, определяет, сопряжены ли заданные ими элементы группы. Примерами автоматных групп являются гиперболические и абелевы. С другой стороны, [8] асинхронно автоматная почти нилыютентная группа — почти абелева, то есть нильпотентная группа может быть автоматной лишь в "вырожденном" случае. Далее, как показано в [9], полициклическая группа может быть подгруппой биав-томатной группы лишь в том случае, если она почти абелева. В целом ситуация выглядит так: в свободных группах и близких к ним имеется хорошая корреляция с автоматами, в разрешимом случае (за исключением абелевых) — плохая. Интересно, что при постановке алгоритмических вопросов для группы не с помощью перевода на язык свободных моноидов, а непосредственно наблюдаются очень похожие явления. Так, например, при изучении вопроса о том, когда рациональные подмножества группы замкнуты не только относительно рациональных операций — объединения, произведения, порождения подмоноида, но и относительно пересечения, дополнения в группе, разности множеств, то есть образуют булеву алгебру множеств, выясняется, что это выполняется для свободных групп, а также для абелевых. С другой стороны, (это основной результат данной диссертации) для полициклических и мета-белевых групп это выполняется лишь в том случае, если группа почти абелева. Опять-таки разрешимый случай оказывается "неавтоматным". К сожалению, для общего случая разрешимой группы задача еще не решена, хотя представляется вполне решаемой.

Целью данной диссертации являлось:

1) дать ответ на вопрос о рациональности множеств решений уравнений от одной неизвестной в классе конечно порожденных нильпотентных групп;

2) дать описание метабелевых, полициклических групп и разрешимых групп типа FP^, у которых классы рациональных подмножеств являются булевыми алгебрами;

3) исследовать класс групп, у которых классы рациональных подмножеств — булевы алгебры, на замкнутость относительно свободных и прямых произведений, подгрупп, факторгрупп и конечных расширений.

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

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

Результаты диссертации докладывались на алгебраическом семинаре Омского университета, на семинаре "Алгебра и логика" Института Математики СО РАН, а также на Международной конференции "Комбинаторные и вычислительные методы в математике" (Омск, 1998).

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

Диссертация состоит из введения и четырех глав, содержащих 8 параграфов. Объем работы — 61 страница, список литературы включает 26 наименований.

Список литературы диссертационного исследования кандидат физико-математических наук Баженова, Галина Александровна, 2000 год

1. Клини С.К. Представление событий в нервных сетях и конечных автоматах, в кн. "Автоматы", М., ИЛ, 1956, с. 15-67.

2. Рабин М.О., Скотт Д. Конечные автоматы и задачи их разрешения, в кн. "Кибернетический сборник", вып. 4, М., ИЛ, 1962, с. 58-91.

3. Хомский Н., Шютценберже М.П. Алгебраическая теория контекстно-свободных языков, в кн. "Кибернетический сборник", новая серия, вып. 3, М., Мир, 1966, с. 195-242.

4. Глушков В.М. Абстрактная теория автоматов, УМН, т.16, N5, с. 3-62.

5. Eilenberg S. Automata, Languages, and, Machines, V A, B, New York, London, Academic Press, 1974, 1976.

6. Лаллеман Ж. Полугруппы и комбинаторные приложения, М., Мир, 1985.

7. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Элементы теории автоматов, М., 1978.

8. Epstein D.B.A., Cannon J.W., Holt D.F., Levy S., Patterson M.S., Thurston W. Word processing in groups, Jones and Bartlett, 1992.

9. Gersten S.M., Short H. Rational subgroups of biautomatic groups, Annals of Math., V 134, 1991, p. 125-158.

10. Epstein D.B.A., Holt D.F., Rees S. The use of Knuth-Bendix methods to solve the word problem in automatic groups, J. Symbolic Computation,V 12, 1991, p. 397-414.

11. Sims C. Computation with Finitely Presented Groups, Encyclopedia of Math, and Its Applications, V 48, Cambridge Univ. Pr., 1994.

12. Gilman R.H. Formal Languages and Infinite Groups, DIMACS Series in Discrete Math, and Theoretical Computer Science, AMS, V 25,1996, p. 27-51.

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

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

15. Robinson D. J.S. Finiteness Conditions and Generalized Soluble Groups, Springer-Verlag, 1972.

16. Kropholler P.H. Hierarchical decompositions, generalized Tate cohomol-ogy, and groups of type (FP)oo, London Math. Society Lecture Note Series, V 204, 1993, p. 190-216.

17. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп, М., Наука, 1982.

18. Киркинский А.С. О пересечениях конечно-порожденных подгрупп в метабелевых группах, Алгебра и логика, 20, N1(1981), 37-54.

19. Roman'kov V.A. On the occurence problem for rational subsets of a group, в сб. научных трудов "Комбинаторные и вычислительные методы в математике", ОмГУ, Омск, 1999, стр. 235-242.Работы автора по теме диссертации

20. Баженова Г.А. О рациональных множествах в конечно порожденных нильпотентных группах, препринт N23, ОмГАУ, Омск, 1999; Алгебра и логика (принято к публикации).

21. Bazhenova G.A. Rational sets in polycyclic groups, в сб. научных трудов " Комбинаторные и вычислительные методы в математике", Ом-ГУ, Омск, 1999, стр. 76-81.

22. Баженова Г.А. Замкнутость одного класса групп относительно свободного произведения, препринт N21, ОмГАУ, Омск, 1999; Сиб. мат. журнал (принято к публикации).

23. Баженова Г.А. О рациональных множествах в метабелевых группах, препринт N22, ОмГАУ, Омск, 1999.

24. Баженова Г.А. О регулярных множествах в группах, Kurosh Algebraic Conference '98, МГУ, Москва, 1998, стр. 137-138.

25. Баженова Г.А. О рациональных множествах в полициклических группах, Тезисы докладов Международной конференции "Комбинаторные и вычислительные методы в математике", ОмГУ, Омск, 1998, стр. 19-20.

26. Баженова Г.А. О почти абелевости некоторых разрешимых групп, препринт (готовится к печати).Г Г*, i"' Г ' '**" л л I' V г J S* к \ Аf 0Cl' ЦА !"U г £ V < ¿ i ÀБИБЛИОТЕКАm-oí