Finitely generated subgroups of free groups as formal languages and their cogrowth

Groups Complexity Cryptology

article

Arman Darbinyan¹  Rostislav Grigorchuk¹  Asif Shaikh¹ 

[1] Department of Mathematics, Texas A&M University, College Station;Department of Mathematics & Statistics, R. A. Podar College of Commerce and Economics

关键词: Free group;    Subgroups;    Schreier graphs;    Cogrowth;    Stallings foldings;    Deterministicfinite automata;    Regular languages;   

DOI  :  10.46298/jgcc.2021.13.2.7617

来源: Episciences

【 摘 要 】

Let H ≤ Fm be a finitely generated subgroup of the free group Fm of finiterank m. It is well-known that the language LH of reduced words from Fm representingelements of H is regular. In the current article, using the (extended) core of the Schreiergraph of H, we construct the minimal deterministic finite automaton that recognizes LH.Then we characterize the finitely generated subgroups H ≤ Fm for which LH is irreducible,and for each such H we explicitly construct an ergodic automaton that recognizes LH.This construction gives us an efficient way to compute the cogrowth series LH(z) as wellas the entropy of LH. Several examples are provided to illustrate the method. Also, acomparison is made with the method of calculation of LH(z) based on the use of Nielsensystem of generators of H.

【 授权许可】

Unknown