5 papers
Topological transitivity of group cellular automata is decidable
Niccolò Castronuovo, Alberto Dennunzio, Luciano Margara
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,…
On solving basic equations over the semiring of functional digraphs
Alberto Dennunzio, Enrico Formenti, Luciano Margara +1
Endowing the set of functional graphs (FGs) with the sum (disjoint union of graphs) and product (standard direct product on graphs) operations induces on FGs a structure of a commu…
Decidability and Characterization of Expansivity for Group Cellular Automata
Niccolo' Castronuovo, Alberto Dennunzio, Luciano Margara
Group cellular automata are continuous, shift-commuting endomorphisms of , where is a finite group. We provide an easy-to-check characterization of expansivity fo…
A Divide and Conquer Algorithm for Deciding Group Cellular Automata Dynamics
Niccolo' Castronuovo, Alberto Dennunzio, Luciano Margara
We prove that many dynamical properties of group cellular automata (i.e., cellular automata defined on any finite group and with global rule which is an endomorphism), including su…
Structural Properties of Non-Linear Cellular Automata: Permutivity, Surjectivity and Reversibility
Firas Ben Ramdhane, Alberto Dennunzio, Luciano Margara +1
This paper explores the algebraic conditions under which a cellular automaton with a non-linear local rule exhibits surjectivity and reversibility. We also analyze the role of perm…