ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2010, ТОМ 16, ВЫПУСК 8, СТР. 189-221

Свободные произведения групп с объединением: стратификация множеств нормальных форм и оценки

А. Г. Мясников
В. Н. Ремесленников
Е. В. Френкель

Аннотация

Посмотреть как HTML    Посмотреть как рисунок

Пусть $A$, $B$, $C$ -- свободные группы конечного ранга, $\$\; G\; =\; \backslash underset\{C\}\{A\; *\; B\}\; \$$ -- свободное произведение групп с объединением. На множестве нормальных форм элементов $G$ в статье введены атомарные меры и соответствующие им асимптотические плотности. Определены две страты для нормальных форм: первая страта регулярных (или стабильных) нормальных форм, вторая -- сингулярных (или нестабильных) нормальных форм. В более ранних работах авторов для классических алгоритмических проблем было показано, что стандартные алгоритмы для свободных конструкций групп работают хорошо на элементах первой страты, но об их работе на второй страте может быть ничего не известно. В данной статье даются вероятностные и асимптотические оценки размеров этих страт.

Полнотекстовая версия статьи в формате PDF (322 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k10/k108/k10810h.htm
Изменения вносились 5 декабря 2011 г.