Measuring cones and other thick subsets in free groups

Document Type : Research Paper

Authors

1 Moscow State University

2 Mathematical Institute SB RAS

Abstract

In this paper we investigate the special automata over finite rank free groups and estimate asymptotic characteristics of sets they accept‎. ‎We show how one can decompose an arbitrary regular subset of a finite rank free group into disjoint union of sets accepted by special automata or special monoids‎. ‎These automata allow us to compute explicitly generating functions‎, ‎$\lambda-$measures and Cesaro measure of thick monoids‎. ‎Also we improve the asymptotic classification of regular subsets in free groups‎.

Keywords

Main Subjects


[1] Ya. S. Averina and E. V. Frenkel, On strictly sparse subsets of a free group, Sib. lektron. Mat. Izv., 2 (2005) 1–13, http://semr.math.nsc.ru.
[2] A. V. Borovik, A. G. Myasnikov and V. N. Remeslennikov, Multiplicative measures on free groups, Internat. J. Algebra Comput., 13 no. 6 (2003) 705--731.
[3] E. Yu. Daniyarova, A. G. Myasnikov and V. N. Remeslennikov, Dimension in universal algebraic geometry, (Russian), translated from Dokl. Akad. Nauk, 457 no. 3 (2014) 265–267.
[4] D. Epstein, J. Cannon, D. Holt, S. Levy, M. Paterson and W. Thurston, Word Processing in Groups, Jones and Bartlett, Boston, 1992.
[5] P. Flajolet and R. Sedgwick, Analytic Combinatorics: Functional Equations, Rational and Algebraic Functions. In: INRIA, RR 4103 2001.
[6] E. Frenkel, A. G. Myasnikov and V. N. Remeslennikov, Regular sets and counting in free groups, Combinatorial and Geometric Group Theory, Trends in Mathematics, Birkhauser Verlag, Basel/Switzerland, 2010 93–118.
[7] E. Frenkel, A. G. Myasnikov and V. N. Remeslennikov, Amalgamated products of groups: measures of random normal forms, Fundam. Prikl. Mat., 16 no. 8 (2010) 189-221.
[8] E. Frenkel and V. N. Remeslennikov, Double cosets in free groups, Internat. J. Algebra Comput., 23 no. 5 (2013) 1225–1241.
[9] E. Frenkel and V. N. Remeslennikov, Cones and thick monoids in free groups, Materials of International Workshop ’Almaz-2’, OmGTU press, Omsk, 2015 64–68.
[10] R. Gilman, Formal languages and their application to combinatorial group theory, Groups, Languages Algorithms, 1-36, Contemp. Math., 378, Amer. Math. Soc., Providence, RI, 2005.
[11] J. G. Kemeny and J. L. Snell, Finite Markov chains, The University Series in Undergraduate Mathematics D. Van Nostrand Co., Inc., Princeton, N. J.-Toronto-London-New York, 1960.
[12] M. V. Lawson, Finite automata, Chapman & Hall, CRC Press, 2004.
[13] M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Develop., 3
no. 2 (1959) 114–125.