Arman Darbinyan ; Rostislav Grigorchuk ; Asif Shaikh - Finitely generated subgroups of free groups as formal languages and their cogrowth

gcc:7617 - journal of Groups, complexity, cryptology, November 16, 2021, volume 13, issue 2 - https://doi.org/10.46298/jgcc.2021.13.2.7617
Finitely generated subgroups of free groups as formal languages and their cogrowth

Authors: 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$.


Volume: volume 13, issue 2
Published on: November 16, 2021
Accepted on: November 8, 2021
Submitted on: June 23, 2021
Keywords: Mathematics - Group Theory,20E07, 68Q45, 68Q70


Share

Consultation statistics

This page has been seen 42 times.
This article's PDF has been downloaded 36 times.