Density of group languages in shift spaces
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909295517368320 |
|---|---|
| author | Berthé, Valérie Goulet-Ouellet, Herman Nyberg-Brodda, Carl-Fredrik Perrin, Dominique Petersen, Karl |
| author_facet | Berthé, Valérie Goulet-Ouellet, Herman Nyberg-Brodda, Carl-Fredrik Perrin, Dominique Petersen, Karl |
| contents | The density of a rational language can be understood as the frequency of some "pattern" in the shift space, for example a pattern like "words with an even number of a given letter." We study the density of group languages, i.e. rational languages recognized by morphisms onto finite groups, inside shift spaces. We show that the density with respect to any given ergodic measure on a shift space exists for every group language, because it can be computed by using any ergodic lift of the given measure to some skew product between the shift space and the recognizing group. We then further study densities in shifts of finite type (with a suitable notion of irreducibility), and then in minimal shifts. In the latter case, we obtain a closed formula for the density under the condition that the skew product has minimal closed invariant subsets which are ergodic under the product of the original measure and the uniform probability measure on the group. The formula is derived in part from a characterization of minimal closed invariant subsets for skew products relying on notions of cocycles and coboundaries. In the case where the whole skew product is ergodic under the product measure, then the density is just the cardinality of the subset of the group which defines the language divided by the cardinality of the group. Moreover, we provide sufficient conditions for the skew product to have minimal closed invariant subsets that are ergodic under the product measure. Finally, we investigate the link between minimal closed invariant subsets, return words and bifix codes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_17892 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Density of group languages in shift spaces Berthé, Valérie Goulet-Ouellet, Herman Nyberg-Brodda, Carl-Fredrik Perrin, Dominique Petersen, Karl Dynamical Systems Discrete Mathematics 37B10 (Primary) 37A20 68Q45 (Secondary) The density of a rational language can be understood as the frequency of some "pattern" in the shift space, for example a pattern like "words with an even number of a given letter." We study the density of group languages, i.e. rational languages recognized by morphisms onto finite groups, inside shift spaces. We show that the density with respect to any given ergodic measure on a shift space exists for every group language, because it can be computed by using any ergodic lift of the given measure to some skew product between the shift space and the recognizing group. We then further study densities in shifts of finite type (with a suitable notion of irreducibility), and then in minimal shifts. In the latter case, we obtain a closed formula for the density under the condition that the skew product has minimal closed invariant subsets which are ergodic under the product of the original measure and the uniform probability measure on the group. The formula is derived in part from a characterization of minimal closed invariant subsets for skew products relying on notions of cocycles and coboundaries. In the case where the whole skew product is ergodic under the product measure, then the density is just the cardinality of the subset of the group which defines the language divided by the cardinality of the group. Moreover, we provide sufficient conditions for the skew product to have minimal closed invariant subsets that are ergodic under the product measure. Finally, we investigate the link between minimal closed invariant subsets, return words and bifix codes. |
| title | Density of group languages in shift spaces |
| topic | Dynamical Systems Discrete Mathematics 37B10 (Primary) 37A20 68Q45 (Secondary) |
| url | https://arxiv.org/abs/2403.17892 |