Graph and wreath products of cellular automata
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918007579607040 |
|---|---|
| author | Salo, Ville |
| author_facet | Salo, Ville |
| contents | We prove that the set of subgroups of the automorphism group of a two-sided full shift is closed under countable graph products. We introduce the notion of a group action without $A$-cancellation (for an abelian group $A$), and show that when $A$ is a finite abelian group and $G$ is a group of cellular automata whose action does not have $A$-cancellation, the wreath product $A \wr G$ embeds in the automorphism group of a full shift. We show that all free abelian groups and free groups admit such cellular automata actions. In the one-sided case, we prove variants of these results with reasonable alphabet blow-ups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2012_10186 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Graph and wreath products of cellular automata Salo, Ville Group Theory Formal Languages and Automata Theory Dynamical Systems We prove that the set of subgroups of the automorphism group of a two-sided full shift is closed under countable graph products. We introduce the notion of a group action without $A$-cancellation (for an abelian group $A$), and show that when $A$ is a finite abelian group and $G$ is a group of cellular automata whose action does not have $A$-cancellation, the wreath product $A \wr G$ embeds in the automorphism group of a full shift. We show that all free abelian groups and free groups admit such cellular automata actions. In the one-sided case, we prove variants of these results with reasonable alphabet blow-ups. |
| title | Graph and wreath products of cellular automata |
| topic | Group Theory Formal Languages and Automata Theory Dynamical Systems |
| url | https://arxiv.org/abs/2012.10186 |