English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse
  1. View item / 
  2. Item Summary

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Journal Article

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

MPS-Authors
/persons/resource/persons235357

Grigorchuk,  Rostislav
Max Planck Institute for Mathematics, Max Planck Society;

External Resource

https://doi.org/10.46298/jgcc.2021.13.2.7617
(Publisher version)

Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
Supplementary Material (public)
There is no public supplementary material available
Citation

Darbinyan, A., Grigorchuk, R., & Shaikh, A. (2021). Finitely generated subgroups of free groups as formal languages and their cogrowth. Journal of groups, complexity, cryptology, 13(2): Paper No. 1. doi:10.46298/jgcc.2021.13.2.7617.


Cite as: https://hdl.handle.net/21.11116/0000-0009-FE5B-4
Abstract
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$.