Алгоритмы, меры и нормальные формы для свободных групповых конструкций

• Автор: Френкель, Елизавета Владимировна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Омск
• Количество страниц: 91 с.

Оглавление
Введение
Глава 1. Меры подмножеств свободной группы и свободных групповых конструкций
1.1. Вычисление меры подгрупп свободного произведения циклических групп
1.1.1. Вычисление мер подгрупп
1.1.2. Мультипликативность меры
1.2. Разреженные и строго разреженные подмножества свободной группы
1.2.1. Регулярные подмножества свободной группы
1.2.2. Определения и простейшие свойства разреженных множеств
1.2.3. Критерий строгой разреженности регулярных подмножеств свободной
группы
1.2.4. Конструкции над строго разреженными множествами
1.3. Разреженность двойного класса смежности по подгруппам бесконечного индекса
Глава 2. Алгоритмы приведения элементов фундаментальных групп конечных графов групп к нормальной форме
2.1. Основные определения
2.2. Случай линейного графа
2.3. «Чупа-чупс»
2.4. Треугольник
2.5. Произвольный случай
2.6. Единственность ц-нормальной формы элемента фундаментальной группы графов црупп
2.6.1. Граф У - дерево
2.6.2. Граф У не является деревом
2.7. Оценка процедуры I
2.8. Модификация алгоритма приведения элементов некоторых фундаментальных групп графов групп к нормальной форме
2.8.1. Краткие сведения о группах Баумслага-Солитера
2.8.2. Модификация алгоритма приведения к нормальной форме
Глава 3. Алгоритм приведения элементов фундаментальной группы конечного графа групп к редуцированной форме
3.1. Определения
3.2. Построение нити для реберной подгруппы графа групп
3.3. Процедура проверки склейки пары элементов вершинных групп
3.4. Проблема вхождения в комплекс АВ
3.5. Процедура устранения расщепления тройки элементов
3.6. Процедура II приведения элементов фундаментальной группы конечного графа групп к редуцированной форме
Литература

Введение
В лекциях, прочитанных Ж.-П. Серром в Колледж де Франс в 1968 — 69 годах, им было введено понятие фундаментальной группы графа групп, обобщающее известные в теории групп понятия свободного произведения с объединением и ЛАТААрасширения. Эти лекции были переработаны и подготовлены к публикации совместно с X. Бассом. В этой работе были описаны свойства фундаментальных групп графов групп на языке групп, действующих на деревьях. Созданная теория, в настоящее время называемая теорией Басса-Серра, помогла существенно упростить доказательства многих теорем комбинаторной теории групп о свободных конструкциях. Эта теория подробно изложена непосредственно в работе Ж.-П. Серра [1], а также в книге О.В. Богопольского [4].
При работе с группами и свободными групповыми конструкциями в частности, необходимо унифицировать запись элемента и для этого вводятся различные нормальные формы: канонические нормальные, редуцированные, циклически
редуцированные. Если для группы найдены хорошие нормальные формы записи элементов, то тогда в ней, как правило, разрешимы и классические алгоритмические проблемы: проблема равенства слов, проблема сопряженности и другие. Для свободных произведений групп, свободных произведений с объединением и НЕМ-расширений групп удобные нормальные формы найдены сравнительно давно; эти нормальные формы приведены, например, в книгах В. Магнуса, А. Карраса и Д. Солитэра [2] и Р. Линдона и П. Шуппа [3].
В диссертации вводится понятие о—нормальной формы (аналог канонических нормальных форм), редуцированной и циклически редуцированной форм элементов фундаментальной группы конечного графа групп. Введенные нормальные формы были апробированы в работе [23], в которой, базируясь на понятии редуцированной формы элемента, Я.С. Аверина нашла критерий сопряженности элементов для фундаментальной группы конечного графа групп. Одним из основных результатов диссертационной работы является построение алгоритма приведения к редуцированной форме записи элемента фундаментальной группы конечного графа групп и оценка его сложности.
В исследовании алгоритмических проблем широкое распространение получила идея стратификации входных данных но сложности рассматриваемых алгоритмических проблем. При стратификации входных данных определяется регулярная часть алгоритма, то есть множество входных данных, на которых алгоритм работает быстро (например, в линейное или квадратичное время), а также дополнение к регулярной

представителей правых смежных классов группы 6/3 по подгруппе Сделаем
небольшое уточнение: правым смежным классом группы б но подгруппе Н называется класс Нд, где д 6 (7. Обозначим р = р?1ип,и2и2-
Для каждого из четырех вложений реберных подгрупп в вершинные группы определим множество нормальных форм.
Определение 2.3. б!-нормальной формой элемента д группы (2.1) называется запись
д = Н Р1 р2 ... рк, (2.2)
где р$ £ Р, у = 1
• р3 и р]+1 — представители для различных вершинных групп,
• элемент к аех{А).
Замечание. Аналогичным образом вводится понятие нормальной формы для оставшихся трех вложений, причем разновидность нормальной формы однозначно определяется выбранным вложением реберной подгруппы в вершинную группу. Отметим, что элемент 1г в записи элемента д принадлежит той подгруппе, которая определяет тип нормальной формы. В дальнейшем мы не будем утомлять читателя перечислением этих нормальных форм и фактов, касающихся каждой из них в отдельности, подразумевая, однако, что все они равноправны. Теперь мы можем сформулировать следующую теорему.
Теорема 2.1. Произвольный элельент д группы 7Гх (<7, У, Т) имеет единственную в! — нормальную форму.
Доказательство существования формы (2.2) следует из процедуры приведения элемента к нормальной форме для линейного графа, которая будет описана ниже. Единственность будет доказана в параграфе 2.6 для произвольного конечного графа групп. Для описания процедуры приведения элемента к нормальной форме нам понадобится следующее
Определение 2.4. Прегрупповой длгтой Ь(у) записи
9 = 01 № Оп, (2.3)
произвольного неединичного элемента д £ 7Гх (й, У,Т), где неединичные элементы дг и 9г+1 принадлежат раэличньш вершинным группам, называется число п. Полагаем также 1/(1) = 0.