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

В лекциях, прочитанных Ж.-ГТ. Серром в Колледж де Франс в 1968 — 69 годах, им было введено понятие фундаментальной группы графа групп, обобщающее известные в теории групп понятия свободного произведения с объединением и НММ-расширения. Эти лекции были переработаны и подготовлены к публикации совместно с X. Бассом. В этой работе были описаны свойства фундаментальных групп графов групп на языке групп, действующих на деревьях. Созданная теория, в настоящее время называемая теорией Басса-Серра, помогла существенно упростить доказательства многих теорем комбинаторной теории групп о свободных конструкциях. Эта теория подробно изложена непосредственно в работе Ж.-П. Серра [1], а также в книге О. В. Богопольского [4].

При работе с группами и свободными групповыми конструкциями в частности, необходимо унифицировать запись элемента и для этого вводятся различные нормальные формы: канонические нормальные, редуцированные, циклически редуцированные. Если для группы найдены хорошие нормальные формы записи элементов, то тогда в ней, как правило, разрешимы и классические алгоритмические проблемы: проблема равенства слов, проблема сопряженности и другие. Для свободных произведений групп, свободных произведений с объединением и ГШ1т-расшнреиий групп удобные нормальные формы найдены сравнительно давноэти нормальные формы приведены, например, в книгах В. Магнуса, А. Карраса и Д. Солитэра (2] и Р. Линдона и П. Шуппа [3].

В диссертации вводится понятие о—нормальной формы (аналог канонических нормальных форм), редуцированной и циклически редуцированной форм элементов фундаментальной группы конечного графа групп. Введенные нормальные формы были апробированы в работе [23], в которой, базируясь на понятии редуцированной формы элемента, Я. С. Аверина нашла критерий сопряженности элементов для фундаментальной группы конечного графа групп. Одним из основных результатов диссертационной работы является построение алгоритма приведения к редуцированной форме записи элемента фундаментальной группы конечного графа групп и оценка его сложности.

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

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

Вероятностные меры на свободных группах были введены в работе А. В. Боровика, А. Г. Мясникова и В. Н. Ремесленникова [8]. В работе [5] эти вероятностные меры были распространены на свободные групповые конструкции и применены для исследования генерической сложности проблемы равенства слов и проблемы сопряженности.

1. Serre J.-P. Trees // Berlin-Heidelberg-New York: Springer-Verlag, 1980.

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

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

4. Богопольский О. В.

Введение

в теорию групп // М.: Современная математика, 2002.

5. Borovik A., Myasnikov A., Remeslennikov V. Multiplicative Measures on the Free Group // International Jornal of4Algebra and Computations 13 (2003), P. 705−731.

6. Epstein D. and others. Word Processing in Groups, Jones and Bartlett Publishers, 19927j Kapovich I., Myasnikov A. Stallings Foldings and Subgroups of Free Groups. // Jornal of Algebra 248 (2002), no 2, P.608 668.

7. Borovik A., Myasnikov A., Remeslennikov V. The Conjugacy Problem in Amalgamated Products I: Regular Elements and Black Holes //to appear: International Jornal of Algebra and Computations.

8. Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: Мир, 1982.

9. Kapovich I., Myasnikov A., Schupp P., Shpilrain V. Generic-Case Complexity Decision Problems in Group Theory and Random Walks // Jornal of Algebra 264 (2003), no 2, P. 665−694.

10. Кнут Д. Искусство программирования // М.:Современная математика, т. З, 2001.

11. Есып Е. С., Ремесленников В. Н. Уравнения от одной переменной над свободными произведениями циклических групп // Препринт ном. 31. Омск: ОмГАУ, 2000.

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

13. Rayward-Smith V. A First Course in Formal Language Theory // Blackwell Scientific Publications, Oxford, 1983.

14. Quenell G. Combinatorics on free product graphs j / Geometry of the spectrum (Seattle, WA, 1993), Amer. Math. Soc., Providence, RI, 1994, pp. 257−281.

15. Bartholdi L. Counting Paths in Graphs // arxiv: math.co/12 161 vl 18 Dec 2000.

16. Аверина Я. С., Френкель E.B. Полиномиальный алгоритм приведения элементов некоторых групп Баумслага-Солитера к нормальной форме // Вестник Омского университета. Вып. 2. 2004. С. 16 18.

17. Аверина Я. С., Френкель Е. В. Разреженность регулярных подмножеств свободной группы // Вестник Омского Университета Выпуск 4, 2004, р. 16 — 18

18. Аверина Я. С., Френкель Е. В. Вычисление меры подгрупп свободного произведения циклических групп // Вестник Омского университета, 2002, выпуск 3(25), с. 13 -15

19. Аверина Я. С., Френкель Е. В. Разреженность классов смежности по подгруппам свободной группы // Препринт№ 00−01, Омск: Омск. Госуниверситет, 2004; 14с.

20. Аверина Я. С., Френкель Е. В. Алгоритм приведения к канонической нормальной форме элел1снтов фундаментальных групп графов групп // Препринт№ 00−02, Омск: Изд-во ОмГУ, 2005 20с.

21. Аверина Я. С., Френкель Е. В. О строго разреженных подмножествах свободной группы // Сибирские электронные математические известия, ISSN 1813−3304, ТОМ 2 (2005), с.1−13, http://semr.math.nsc.ru

22. Аверина Я. С. Критерий сопряженности для элементов фундаментальной группы конечного графа групп // Препринт № 00−03, Омск: Отдел оперативной полиграфии фирмы «Банковский сервис», 2006 16 с.

23. Френкель Е. В. Алгоритм приведения элементов фундаментальной группы конечного графа групп к редуцированной форме // Препринт № 00−04, Омск: Отдел оперативной полиграфии фирмы «Банковский сервис», 2006 36 с.