episciences.org_7617_1643076917
1643076917
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
journal of Groups, complexity, cryptology
1869-6104
10.46298/journals/jgcc
https://gcc.episciences.org
11
16
2021
Volume 13, Issue 2
Finitely generated subgroups of free groups as formal languages and
their cogrowth
Arman
Darbinyan
Rostislav
Grigorchuk
Asif
Shaikh
For finitely generated subgroups $H$ of a free group $F_m$ of finite rank
$m$, we study the language $L_H$ of reduced words that represent $H$ which is a
regular language. Using the (extended) core of Schreier graph of $H$, we
construct the minimal deterministic finite automaton that recognizes $L_H$.
Then we characterize the f.g. subgroups $H$ for which $L_H$ is irreducible and
for such groups explicitly construct ergodic automaton that recognizes $L_H$.
This construction gives us an efficient way to compute the cogrowth series
$L_H(z)$ of $H$ and entropy of $L_H$. Several examples illustrate the method
and a comparison is made with the method of calculation of $L_H(z)$ based on
the use of Nielsen system of generators of $H$.
11
16
2021
7617
arXiv:2106.11552
10.46298/jgcc.2021.13.2.7617
https://gcc.episciences.org/7617