Topological transitivity of group cellular automata is decidable
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909998727036928 |
|---|---|
| author | Castronuovo, Niccolò Dennunzio, Alberto Margara, Luciano |
| author_facet | Castronuovo, Niccolò Dennunzio, Alberto Margara, Luciano |
| contents | Topological transitivity is a fundamental notion in topological dynamics and is widely regarded as a basic indicator of global dynamical complexity. For general cellular automata, topological transitivity is known to be undecidable. By contrast, positive decidability results have been established for one-dimensional group cellular automata over abelian groups, while the extension to higher dimensions and to non-abelian groups has remained an open problem. In this work, we settle this problem by proving that topological transitivity is decidable for the class of $d$-dimensional ($d\geq 1$) group cellular automata over arbitrary finite groups. Our approach combines a decomposition technique for group cellular automata, reducing the problem to the analysis of simpler components, with an extension of several results from the existing literature in the one-dimensional setting. As a consequence of our results, and exploiting known equivalences among dynamical properties for group cellular automata, we also obtain the decidability of several related notions, including total transitivity, topological mixing and weak mixing, weak and strong ergodic mixing, and ergodicity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_16243 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Topological transitivity of group cellular automata is decidable Castronuovo, Niccolò Dennunzio, Alberto Margara, Luciano Formal Languages and Automata Theory Discrete Mathematics Dynamical Systems Topological transitivity is a fundamental notion in topological dynamics and is widely regarded as a basic indicator of global dynamical complexity. For general cellular automata, topological transitivity is known to be undecidable. By contrast, positive decidability results have been established for one-dimensional group cellular automata over abelian groups, while the extension to higher dimensions and to non-abelian groups has remained an open problem. In this work, we settle this problem by proving that topological transitivity is decidable for the class of $d$-dimensional ($d\geq 1$) group cellular automata over arbitrary finite groups. Our approach combines a decomposition technique for group cellular automata, reducing the problem to the analysis of simpler components, with an extension of several results from the existing literature in the one-dimensional setting. As a consequence of our results, and exploiting known equivalences among dynamical properties for group cellular automata, we also obtain the decidability of several related notions, including total transitivity, topological mixing and weak mixing, weak and strong ergodic mixing, and ergodicity. |
| title | Topological transitivity of group cellular automata is decidable |
| topic | Formal Languages and Automata Theory Discrete Mathematics Dynamical Systems |
| url | https://arxiv.org/abs/2601.16243 |