FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2010, VOLUME 16, NUMBER 8, PAGES 189-221

Amalgamated products of groups: measures of random normal forms

A. G. Myasnikov
V. N. Remeslennikov
E. V. Frenkel

Abstract

View as HTML     View as gif image

Let $\$\; G\; =\; \backslash underset\{C\}\{A\; *\; B\}\; \$$ be an amalgamated product of finite rank free groups $A$, $B$, and $C$. We introduce atomic measures and corresponding asymptotic densities on a set of normal forms of elements in $G$. We also define two strata of normal forms: the first one consists of regular (or stable) normal forms, and the second stratum is formed by singular (or unstable) normal forms. In a series of previous works about classical algorithmic problems, it was shown that standard algorithms work fast on elements of the first stratum and nothing is known about their work on the second stratum. In this paper, we give probabilistic and asymptotic estimates of these strata.

Location: http://mech.math.msu.su/~fpm/eng/k10/k108/k10810h.htm
Last modified: December 5, 2011