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