{"id":"arxiv/2601.16243","url":"https://arxiv.org/abs/2601.16243","tags":["cs.FL","cs.DM","math.DS"],"score":0,"title":"Topological transitivity of group cellular automata is decidable","domain":"cs.FL","source":"arxiv","authors":["Niccolò Castronuovo","Alberto Dennunzio","Luciano Margara"],"reviews":0,"subject":"cs.FL","summary":"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$)…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-22","reactions":{}}