×

Amalgamated products of groups: measures of random normal forms. (English. Russian original) Zbl 1259.20032

J. Math. Sci., New York 185, No. 2, 300-320 (2012); translation from Fundam. Prikl. Mat. 16, No. 8, 189-221 (2010).
Summary: Let \(G=A*_CB\) 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.

MSC:

20E05 Free nonabelian groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20E06 Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations
20F69 Asymptotic properties of groups
20P05 Probabilistic methods in group theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] G. Arzhantseva and P.-A. Cherix, ”On the Cayley graph of a generic finitely presented group,” Bull. Belg. Math. Soc. Simon Stevin, 11, No. 4, 589–601 (2004). · Zbl 1069.05038
[2] Ya. S. Averina and E. V. Frenkel, ”On strictly sparse subsets of a free group,” Sib. Electron. Math. Reports, 2, 1–13 (2005), http://semr.math.nsc.ru . · Zbl 1126.20301
[3] A. V. Borovik, A. G. Myasnikov, and V. N. Remeslennikov, ”Multiplicative measures on free groups,” Int. J. Algebra Comput., 13, No. 6, 705–731 (2003). · Zbl 1061.20066 · doi:10.1142/S0218196703001596
[4] A. V. Borovik, A. G. Myasnikov, and V. N. Remeslennikov, ”Algorithmic stratification of the conjugacy problem in Miller’s groups,” Int. J. Algebra Comput., 17, No. 5-6, 963–997 (2007). · Zbl 1171.20016 · doi:10.1142/S0218196707003913
[5] A. V. Borovik, A. G. Myasnikov, and V. N. Remeslennikov, ”The conjugacy problem in amalgamated products I: regular elements and black holes,” Int. J. Algebra Comput., 17, No. 7, 1301–1335 (2007). · Zbl 1149.20025
[6] D. Epstein, J. Cannon, D. Holt, S. Levy, M. Paterson, and W. Thurston, Word Processing in Groups, Jones and Bartlett, Boston (1992). · Zbl 0764.20017
[7] E. Frenkel, A. G. Myasnikov, and V. N. Remeslennikov, ”Regular sets and counting in free groups,” in: O. Bogopolski, ed., 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, and the Workshop on ”Action on Trees, Non-Archimedian Words, and Asymptotic Cones,” Montreal, Canada, December 17–21, 2007, Trends Math., Birkhäuser, Basel (2010), pp. 93–118. · Zbl 1211.20024
[8] R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, Report on generic case complexity, Vestn. Omsk. Univ., Special Issue, 103–110 (2007).
[9] I. Kapovich and A. G. Myasnikov, ”Stallings foldings and subgroups of free groups,” J. Algebra, 248, 608–668 (2002). · Zbl 1001.20015 · doi:10.1006/jabr.2001.9033
[10] J. G. Kemeny and J. L. Snell, Finite Markov Chains, Van Nostrand, Princeton (1960).
[11] R. C. Lyndon and P. Schupp, Combinatorial Group Theory, Ergebnisse Math. ihrer Grenzgebiete, Vol. 89, Springer, Berlin (1977). · Zbl 0368.20023
[12] W. Magnus, A. Karras, and D. Solitar, Combinatorial Group Theory, Interscience Publishers, New York (1966).
[13] C. F. Miller III, On Group-Theoretic Decision Problems and Their Classification, Ann. Math. Stud., No. 68, Princeton Univ. Press, Princeton (1971). · Zbl 0277.20054
[14] W. Woess, ”Cogrowth of groups and simple random walks,” Arch. Math., 41, 363–370 (1983). · Zbl 0522.20043 · doi:10.1007/BF01371408
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.