Finitely generated subgroups of free groups as formal languages and their cogrowth
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Episciences
2021-11-01
|
| Series: | Groups, Complexity, Cryptology |
| Subjects: | |
| Online Access: | https://gcc.episciences.org/7617/pdf |
| _version_ | 1797986399179243520 |
|---|---|
| author | Arman Darbinyan Rostislav Grigorchuk Asif Shaikh |
| author_facet | Arman Darbinyan Rostislav Grigorchuk Asif Shaikh |
| author_sort | Arman Darbinyan |
| collection | DOAJ |
| description | 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$. |
| first_indexed | 2024-04-11T07:33:22Z |
| format | Article |
| id | doaj.art-b27ebad209fb486d816562f01bcc6cea |
| institution | Directory Open Access Journal |
| issn | 1869-6104 |
| language | English |
| last_indexed | 2024-04-11T07:33:22Z |
| publishDate | 2021-11-01 |
| publisher | Episciences |
| record_format | Article |
| series | Groups, Complexity, Cryptology |
| spelling | doaj.art-b27ebad209fb486d816562f01bcc6cea2022-12-22T04:36:50ZengEpisciencesGroups, Complexity, Cryptology1869-61042021-11-01Volume 13, Issue 210.46298/jgcc.2021.13.2.76177617Finitely generated subgroups of free groups as formal languages and their cogrowthArman DarbinyanRostislav GrigorchukAsif ShaikhFor 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$.https://gcc.episciences.org/7617/pdfmathematics - group theory20e07, 68q45, 68q70 |
| spellingShingle | Arman Darbinyan Rostislav Grigorchuk Asif Shaikh Finitely generated subgroups of free groups as formal languages and their cogrowth Groups, Complexity, Cryptology mathematics - group theory 20e07, 68q45, 68q70 |
| title | Finitely generated subgroups of free groups as formal languages and their cogrowth |
| title_full | Finitely generated subgroups of free groups as formal languages and their cogrowth |
| title_fullStr | Finitely generated subgroups of free groups as formal languages and their cogrowth |
| title_full_unstemmed | Finitely generated subgroups of free groups as formal languages and their cogrowth |
| title_short | Finitely generated subgroups of free groups as formal languages and their cogrowth |
| title_sort | finitely generated subgroups of free groups as formal languages and their cogrowth |
| topic | mathematics - group theory 20e07, 68q45, 68q70 |
| url | https://gcc.episciences.org/7617/pdf |
| work_keys_str_mv | AT armandarbinyan finitelygeneratedsubgroupsoffreegroupsasformallanguagesandtheircogrowth AT rostislavgrigorchuk finitelygeneratedsubgroupsoffreegroupsasformallanguagesandtheircogrowth AT asifshaikh finitelygeneratedsubgroupsoffreegroupsasformallanguagesandtheircogrowth |