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

Министерство образования РФ Омский государственный университет

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

Баженова Галина Александровна ? Г Б ОД

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

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

^ М т

Омск - 2000

Работа выполнена на кафедре информационных систем Омского государственного университета.

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

Официальные оппоненты

д. ф. - м. наук, профессор В. А. Романьков.

д. ф. - м. наук, профессор Л. М. Мартынов,

д. ф. - м. наук, профессор Н. С. Романовский.

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

Новосибирский государственный

архитектурно-строительный

университет

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

2000 г. в

часов на заседании

диссертационного совета К 06436.02 при Омском государственном университете по адресу: 644077, Омск, пр. Мира, 55А.

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

Автореферат разослан

2000 г.

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

д. ф. - м. наук, профессор

/

, В. А. Романьков

»

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

Содержание диссертации

Сначала приведем некоторые определения.

Определение 1.1. Пустъ М — моноид, или полугруппа с единицей. По индукции определим классы Щ.г = 0,1,..., подмножеств из М следующим образом:

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

2. Если классы 7Za,... ,7Zn уже определены, то определим TZn+i как класс всех множеств S С М таких, что S не принадлежит ни одному из классов TZ0l... ,7Zn, но существуют множества 7\ £ lZk,T2 £ 7Zi, 0 < k,l < п такие, что либо S = 7\ \JT2, либо S = 71 Хг = {ab\a € 71, Ь 6 7г}, либо S = 7? = {1} UТ, UTiTx и Т^Т, U.. ..

Объединение всех классов IZi, г = 0,1,..., называется классом рациональных подмножеств М и обозначается 7Z(M).

Если множество S С М принадлежит TZk, то число к будем называть сложностью множества S.

Хорошо известно (см., например, [12]) следующее описание рациональных множеств с помощью конечных автоматов.

Определение 1.2. Конечным автоматом Г над моноидом М называется четверка (Q,qo,Qt,&), где Q - конечное множество ('множество вершин,), go - элемент Q (начальная вершина,), Qt - подмножество Q ('множество выходных вершин,), Q - конечное подмножество декартова произведения Q х М х Q ('множество стрелок/

Правильный путь 7Г б автомате Г - это конечная последовательность стрелок вида uj\,... ,и>п, где щ = (д;_х, гггг-, дг-), причем qn £ Qt. Меткой стрелки u>i называется элемент т,-. Меткой пути л называется произведение гп\ • ■ ■ тп.

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

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

Следующая лемма дает полезное необходимое условие рациональности множества. В основе ее доказательства лежит хорошо известная и широко используемая идея, а именно то, что в конечном автомате лишь конечное число путей без петель, то есть без возвращения в уже пройденные вершины. В англоязычной литературе утверждения такого типа принято называть Pumping lemma, или "лемма о накачивании". Мы приводим ее здесь как образец типичной техники.

Лемма 1.1. [20] Пусть М — моноид, и Я € И(М). Тогда

1) либо Я конечно, либо существуют такие и, из М, что V ф 1 и для всех целых п > 0 элемент принадлежит Я;

2) существуют такие конечные множества Т0,Тх С М, что 1 ^ 7\ и любое т из Д\7о можно представить в виде т = иЬь так, что í €

и Ы'ь С Я.

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

Пусть М\ С М2 - моноиды, Я С Мг. Тогда если Я - рациональное подмножество М\, то оно - рациональное подмножество М2. Обратное, вообще говоря, неверно. Однако, как показывает следующее предложение, если М\ и М-} являются группами, то верно и обратное.

Лемма 1.2. [13, 20] Пусть Н < С — группы, и множество Я С Я принадлежит 7£((7). Тогда Я € 71(Н).

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

Определение 2.1. Пусть (? - к. п. группа, А - конечный алфавит, Д*

- свободный моноид, А : А* —> (? - сюръективный морфизм моноидов, Ь € %{А") и А(Ь) = С. Тогда пара (Д, Л) называется выбором порождающих для (?, тройка (Л, А, Ь) называется рациональной структурой на С. Множество ДС б называется Ь - рациональным, если А""1 (Я) П Ь рационально. (Это не означает, что выбор порождающих фиксирован; имеется в виду, что "информация о А и А содержится в Ь".)

Поскольку морфизмы моноидов переводят рациональные множества в рациональные, то ¿-рациональное для некоторого Ь множество рационально. С другой стороны, нетрудно привести пример множества И С Z2, Ь-рационального для одного Ь, но не ¿-рационального для другого Ь. (Пусть, например, а и Ь свободно порождают Z2, А — {х, X, у, У}

— алфавит, Ь = х*у*иХ*у*^х*У*'ОХ*У*, а В. — а*. Тогда если интерпретировать буквы из Д как х = а, у = Ь, X = а-1, К = б-1, то множество Я будет Х-рациональным, а если х = аЬ,у = Ь,Х = а~1Ъ~1,У = ¿г1, то нет.) Следующая теорема дает критерий того, что любое рациональное множество является Ь-рациональным для некоторого Ь.

Теорема 2.1. [20] Пусть С - к. п. группа. Тогда следуюище условия эквивалентны:

1) — булева алгебра, то есть замкнут относительно объединения, пересечения, дополнения, теоретико-множественной разности.

2) Любое множество из класса Ь - рационально для некоторого Ь.

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

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

2) Доказано, что если рациональные подмножества полициклической или метабелевой группы образуют булеву алгебру, то эта группа почти абелева (Теоремы 5.1, 6.2). Аналогично, если рациональные подмножества разрешимой группы типа РР,х образуют булеву алгебру, то эта группа почти абелева (Теорема 8.2).

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

Глава I посвящена, в основном, изучению вопроса о рациональности множеств решений уравнений над конечно порожденными нильпотент-ными группами. Напомним, что в свободной группе конечного ранга любое уравнение от одной неизвестной имеет рациональное множество решений [14]. Кроме того, нетрудно доказать, что аналогичное утверждение верно для к. п. абелевых групп. В параграфе 3 данной диссертации доказано, что в конечно порожденной двуступенно нильпотентной группе любое уравнение от одной неизвестной имеет рациональное множество решений, а также приведен пример уравнения от одной неизвестной в свободной нильпотентной группе ранга два и ступени три, множество решений которого не рационально, что решает известную в этой области проблему о существовании таких уравнений над к. п. ниль-

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

Определение 3.1. Уравнением от одной неизвестной х с коэффициентами в группе С называется выражение вида

... дпх£п = 1, где ^ еС,Е; = ± 1 (г = 1,..., п).

Лемма 3.1. [20] Пусть К — группа, б — ее подгруппа, Н — нормальная подгруппа С, и пусть [К, С] С Н. Пусть периодическая часть абе-левой группы С?/// конечна. Предположим, что любое уравнение вида

а1ХС1а2Х£г ■ ■ -апх£" = 1, (1)

где ai € '■= ±1,г = 1 ,...,п, х - неизвестная, в = ф О,

имеет в Н конечное множество решений. Тогда любое уравнение вида (1) имеет в С конечное множество решений.

Лемма 3.2. [20] Пусть К - к. п. нильпотентная группа. Тогда любое уравнение вида (1) имеет в К конечное множество решений.

Замечание 3.1. Хорошо известно, что к. п. нильпотентная группа без кручения К имеет центральный ряд, факторы которого — без кручения. Поэтому для такой группы Леммы 3.1 и 3.2 можно уточнить: любое уравнение вида (1) либо не имеет решений, либо имеет единственное решение.

Теорема 3.1. [20] Пусть б - к. п. двуступенно нильпотентная группа. Тогда любое уравнение над С от одной неизвестной имеет в (3 рациональное множество решений.

Если к.п. группа (7 нильпотентна ступени > 3, то любое уравнение от одной неизвестной, сумма показателей при которой не равна нулю, имеет в б конечное множество р.ешений (Лемма 3.2). Как показывает следующий пример, в случае, когда эта сумма равна нулю, множество решений может быть даже не рациональным. (Хотя в свободной нильпо-тентной группе ступени три и ранга два, например, выписанное наугад уравнение скорее всего будет иметь рациональное множество решений.)

Пример 3.1. [20] Пусть б — свободная нилъпотептная группа ступени три и ранга два со свободными порождающими а,Ь. Множество Б решений уравнения [х, а] = [х, Ь.х] б <? не рационально.

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

Пример 3.2. [20] Пусть С? — свободная нильпотентная группа ступени два и ранга два со свободными порождающими а, Ь. Тогда множество решений уравнения \х.у] — 1 не рационально в б х б, то есть множество Б = {{х,у) 6 <3 х (?|[х,;/] = 1} не рационально.

Глава II содержит результаты, касающиеся вопроса о том, в каких группах класс рациональных подмножеств является булевой алгеброй. Напомним, что (см., например, [12]) рациональные подмножества свободного к. п. моноида образуют булеву алгебру, т.е. класс, замкнутый относительно объединения, пересечения, дополнения, теоретико-множественной разности. (Разумеется, если речь идет о классе рациональных подмножеств, то достаточно говорить о замкнутости относительно дополнения, поскольку по определению имеется замкнутость относительно объединения.) Рациональные подмножества свободных групп конечного ранга и к.п. почти абелевых групп — также булевы алгебры.

Основные результаты данпой главы таковы:

Теорема 5.1. [21] Пусть С — полициклическая группа. Если класс ее рациональных подмножеств — булева алгебра, то С почти абелева.

В параграфе б мы доказываем, что метабелева группа, рациональные подмножества которой — булева алгебра, является почти абелевой. Для этого мы используем данное в [18] описание конечно порожденных ме-габелевых групп со свойством Хаусона.

Определение 6.1. Говорят, что группа С обладает свойством Хау-сона, если пересечение любых двух ее к.п. подгрупп - к.п. подгруппа.

Из Леммы 1.2 следует, что если Н < К — группы, то Я 6. И(К) тогда и только тогда, когда Я к.п.. (Это доказано также в [12].) Поэтому если 71{К) - булева алгебра, то К обладает свойством Хаусона. Это позволяет нам использовать результат из [18]. Напомним также, что если ЩК) — булева алгебра, то К конечно порождена.

Теорема 6.1. [18] Пусть в - к.п. метабелева неполициклическал группа. Тогда следующие условия эквивалентны:

1. б - группа со свойством Хаусона.

2. В й есть ряд

1 < Т <1 Я < в, (2)

где |Т| < оо, |С : Я| < оо, Я/Т ~ дгоир(х, о||[а, ах'] = 1, г € 2; = 1), где / - неприводимый над 2 целочисленный многочлен степени т > 0, причем для любого целого п многочлен /(х) не является делителем никакого многочлена степени т — 1 от хп.

(Здесь оАх) = (а1")« •••(а*)9"-1 а«-, если/(.г) = д0хт + ■ ■ ■ + гх + qrn, а ах' — х~гахг.)

Теорема 6.2. [23] Пусть (7 — метабелева группа, и класс И{С) - булева алгебра. Тогда (3 почти абелева.

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

Теорема 7.1. [22] Пусть С,Н — группы. Пусть классы их рациональных подмножеств — булевы алгебры. Тогда класс рациональных подмножеств их свободного произведения С*Н — также булева алгебра.

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

контрпример. Однако, используя одну идею Г. А. Носкова, удалось доказать данное утверждение для некоторого важного подкласса разрешимых групп, а именно для разрешимых групп типа FP^,. Доказательство существенно опирается на результаты о группах с различными условиями конечности, а также на теорему П. Крофоллера о том, что разрешимые группы типа FPca имеют конечную виртуальную когомологическую размерность. Данная глава посвящена изложению этого результата (теорема 8.2).

Вначале приведем основные определения.

Определение 8.1. Группа G называется группой типа b Р^, если для нее существует проективная резольвента ... —> Рп —У ...—>■ Р2 —> Pi —» Po —)■ Z —> 0 конечного типа, то есть такая, что все Pj конечно порождены.

Определение 8.2. Группа G имеет конечную когомологическую размерность, если для нее существует проективная резольвента ... —> Рп Р2 —>■ Р\ -Л Pq —> Z —> 0 конечной длины, то есть такая,

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

Следующая теорема П. Крофоллера является главным "ингредиентом" доказательства основного результата данной главы.

Теорема 8.1. [16] Пусть G — разрешимая группа типа РРЖ. Тогда найдется такая подгруппа конечного индекса Н < G, что Н имеет конечную когомологическую размерность.

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

Теорема 8.2. [26] Пусть G — разрешимая группа типа FPрациональные подмножества которой образуют булеву алгебру. Тогда G — конечно порожденная почти абелева группа.

Замечание 8.1. Доказательство предыдущей теоремы использует идею (известную автору от Г.А. Носкова), которая позволяет доказать, что разрешимая биавтоматная группа G почти абелева. Это дает ответ на известный вопрос о существовании не почти абелевых разрешимых биавтоматных групп (см. [8]).

ВлаГОДарНОСТЬ. Автор благодарит научного руководителя В.А. Романькова за постановку задачи и большую поддержку, В.Н. Ре-месленникова за внимание к работе.

Литература

[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 ofbiautomatic 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, aid 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)K, 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] Баженова Г.А. О почти абелевости некоторых разрешимых групп, препринт (готовится к печати).

Введение

Содержание диссертации 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 наименований.

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í