Geodesic
Amalgamated products of groups: measures of random normal forms
Fundamentalʹnaâ i prikladnaâ matematika, Tome 16 (2010) no. 8, pp. 189-221 
A. G. Myasnikov; V. N. Remeslennikov; E. V. Frenkel. Amalgamated products of groups: measures of random normal forms. Fundamentalʹnaâ i prikladnaâ matematika, Tome 16 (2010) no. 8, pp. 189-221. http://geodesic.mathdoc.fr/item/FPM_2010_16_8_a9/
@article{FPM_2010_16_8_a9,
     author = {A. G. Myasnikov and V. N. Remeslennikov and E. V. Frenkel},
     title = {Amalgamated products of groups: measures of random normal forms},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {189--221},
     year = {2010},
     volume = {16},
     number = {8},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2010_16_8_a9/}
}
TY  - JOUR
AU  - A. G. Myasnikov
AU  - V. N. Remeslennikov
AU  - E. V. Frenkel
TI  - Amalgamated products of groups: measures of random normal forms
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2010
SP  - 189
EP  - 221
VL  - 16
IS  - 8
UR  - http://geodesic.mathdoc.fr/item/FPM_2010_16_8_a9/
LA  - ru
ID  - FPM_2010_16_8_a9
ER  - 
%0 Journal Article
%A A. G. Myasnikov
%A V. N. Remeslennikov
%A E. V. Frenkel
%T Amalgamated products of groups: measures of random normal forms
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2010
%P 189-221
%V 16
%N 8
%U http://geodesic.mathdoc.fr/item/FPM_2010_16_8_a9/
%G ru
%F FPM_2010_16_8_a9

Voir la notice de l'article provenant de la source Math-Net.Ru

Let $G=\mathop{A\ast B}\limits_C$ 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.

[1] Averina Ya. S., Frenkel E. V., “O strogo razrezhennykh podmnozhestvakh svobodnoi gruppy”, Sib. elektron. mat. izv., 2 (2005), 1–13 | MR | Zbl

[2] Lindon R., Shupp P., Kombinatornaya teoriya grupp, Mir, M., 1980 | MR

[3] Magnus V., Karrass A., Soliter D., Kombinatornaya teoriya grupp, Nauka, M., 1974 | MR | Zbl

[4] Arzhantseva G., Cherix P.-A., “On the Cayley graph of a generic finitely presented group”, Bull. Belg. Math. Soc. Simon Stevin, 11:4 (2004), 589–601 | MR | Zbl

[5] Borovik A. V., Myasnikov A. G., Remeslennikov V. N., “Multiplicative measures on free groups”, Int. J. Algebra Comput., 13:6 (2003), 705–731 | DOI | MR | Zbl

[6] Borovik A. V., Myasnikov A. G., Remeslennikov V. N., “Algorithmic stratification of the conjugacy problem in Miller's groups”, Int. J. Algebra Comput., 17:5–6 (2007), 963–997 | DOI | MR | Zbl

[7] Borovik A. V., Myasnikov A. G., Remeslennikov V. N., “The conjugacy problem in amalgamated products I: regular elements and black holes”, Int. J. Algebra Comput., 17:7 (2007), 1301–1335 | DOI | MR

[8] Epstein D., Cannon J., Holt D., Levy S., Paterson M., Thurston W., Word Processing in Groups, Jones and Bartlett, Boston, 1992 | MR | Zbl

[9] Frenkel E., Myasnikov A. G., Remeslennikov V. N., “Regular sets and counting in free groups”, Combinatorial and Geometric Group Theory, Dortmund and Ottawa–Montreal Conferences. Selected Papers of the Conferences on “Combinatorial and Geometric Group Theory with Applications”, GAGTA (Dortmund, Germany, August 27–31, 2007), “ Fields Workshop in Asymptotic Group Theory and Cryptography” (Ottawa, Canada, December 14–16, 2007), the Workshop on “Action on Trees, Non-Archimedian Words, and Asymptotic Cones” (Montreal, Canada, December 17–21, 2007), Trends Math., ed. O. Bogopolski, Birkhäuser, Basel, 2010, 93–118 | MR | Zbl

[10] Gilman R., Miasnikov A. G., Myasnikov A. D., Ushakov A., “Report on generic case complexity”, Vestn. Omsk. univ., 2007, Spets. vyp., 103–110

[11] Kapovich I., Myasnikov A. G., “Stallings foldings and subgroups of free groups”, J. Algebra, 248 (2002), 608–668 | DOI | MR | Zbl

[12] Kemeny J. G., Snell J. L., Finite Markov chains, Van Nostrand, Princeton, 1960 | MR | Zbl

[13] Miller C. F., III, On Group-Theoretic Decision Problems and Their Classification, Ann. Math. Studies, 68, Princeton Univ. Press, Princeton, 1971 | MR | Zbl

[14] Woess W., “Cogrowth of groups and simple random walks”, Arch. Math., 41 (1983), 363–370 | DOI | MR | Zbl