10.46298/jgcc.2021.13.2.7617
Darbinyan, Arman
Arman
Darbinyan
Grigorchuk, Rostislav
Rostislav
Grigorchuk
Shaikh, Asif
Asif
Shaikh
Finitely generated subgroups of free groups as formal languages and
their cogrowth
episciences.org
2021
Mathematics - Group Theory
20E07, 68Q45, 68Q70
contact@episciences.org
episciences.org
2021-06-23T20:50:41+02:00
2021-11-16T05:03:24+01:00
2021-11-16
eng
Journal article
https://gcc.episciences.org/7617
arXiv:2106.11552
1869-6104
PDF
1
journal of Groups, complexity, cryptology ; Volume 13, Issue 2 ; 1869-6104
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$.
Comment: 35 pages, 8 figures, revised version, to appear in journal of Groups,
Complexity and Cryptology