Geodesic
On strictly sparse subsets of a free group
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 2 (2005), pp. 1-13 
J. S. Averina; E. V. Frenkel. On strictly sparse subsets of a free group. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 2 (2005), pp. 1-13. http://geodesic.mathdoc.fr/item/SEMR_2005_2_a0/
@article{SEMR_2005_2_a0,
     author = {J. S. Averina and E. V. Frenkel},
     title = {On strictly sparse subsets of a~free group},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1--13},
     year = {2005},
     volume = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2005_2_a0/}
}
TY  - JOUR
AU  - J. S. Averina
AU  - E. V. Frenkel
TI  - On strictly sparse subsets of a free group
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2005
SP  - 1
EP  - 13
VL  - 2
UR  - http://geodesic.mathdoc.fr/item/SEMR_2005_2_a0/
LA  - ru
ID  - SEMR_2005_2_a0
ER  - 
%0 Journal Article
%A J. S. Averina
%A E. V. Frenkel
%T On strictly sparse subsets of a free group
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2005
%P 1-13
%V 2
%U http://geodesic.mathdoc.fr/item/SEMR_2005_2_a0/
%G ru
%F SEMR_2005_2_a0

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

This paper is motivated by needs of practical computations in finitely generated groups. In the most of the computations in finitely generated groups $G$ the elements are represented as freely reduced words in the free group $F$. In [1] a family of probability measures was used for estimating the complexity of algorithms on groups and subsets of $F$ were classified according to these measures. We find out which regular sets are sparse, i.e. small with respect to the probability measures.

[1] A. V. Borovik, A. G. Myasnikov, V. N. Remeslennikov, “Multiplicative measures on free groups”, International Journal of Algebra and Computation, 13 (2003), 705–731 | DOI | MR | Zbl

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

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

[4] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain, Generic-Case Complexity Decision Problems in Group Theory and Random Walks, March 27, 2002 | MR

[5] David B. A. Epstein et al., Word Processing in Groups, Jones and Bartlett Publishers, 1992 | MR

[6] M. I. Kargapolov, Yu. I. Merzlyakov, Osnovy teorii grupp, Nauka, M., 1977 | MR | Zbl

[7] A. V. Borovik, A. G. Myasnikov, V. N. Remeslennikov, Algorithms for Amalgamated Products, Manchester Center for Pure Mathematics Preprint Series, 2004

[8] Ya. S. Averina, E. V. Frenkel, “Razrezhennost regulyarnykh podmnozhestv svobodnoi gruppy”, Vestnik Omskogo Universiteta, 2004, no. 4, 16–18

[9] Ya. S. Averina, E. V. Frenkel, Razrezhennost klassov smezhnosti po podgruppam svobodnoi gruppy, Preprint No 00-01, OmGU, 2004