We prove that many dynamical properties of group cellular automata (GCA) can be decided by decomposing them into a set of much simpler GCA, provided those properties are decidable for such simpler GCA. Specifically, we provide a novel algorithmic technique that decomposes the GCA under investigation into a finite number of GCA, some defined on abelian groups, while others, if any, on products of simple non-abelian isomorphic groups. Importantly, the groups resulting from the decomposition depend only on the original group and are therefore completely independent of both the automaton and the considered property. Consequently, they do not inherit any aspect of the complexity of the automaton under investigation. We study the inheritance of the dynamical properties in the original GCA versus the same properties in the GCA obtained through decomposition. The latter turn out to be significantly easier to analyze than in the original GCA. Then, we show that injectivity, surjectivity, and equicontinuity/sensitivity to initial conditions can be decided by testing them in the smaller GCA produced by the decomposition. Moreover, we prove that the topological entropy of a GCA can be computed, provided one knows how to compute it for GCA defined on products of simple non-abelian isomorphic groups – for which we explicitly prove how to compute it in the surjective case – and on abelian groups. Finally, we prove that no strongly transitive, and therefore no positively expansive, GCA defined on non-abelian groups exist.

We provide an efficient algorithm deciding chaos for linear cellular automata (LCA) over (Z/mZ)n, a large and important class of cellular automata (CA) which may exhibit many of the complex features typical of general CA and are used in many applications. The efficiency of our algorithm is mainly due to fact that it avoids the computation of the prime factor decomposition of m which is a well-known difficult task. Instead of factoring m we make use of a new and efficient generalized technique for computing the greatest common divisor (gcd) of polynomials with coefficients not belonging to a field, which in itself is an interesting result. We wish also to emphasize that the gcd computations required by our algorithm always involve polynomials of degree at most n. We also illustrate the impact of our algorithm in real-world applications regarding the growing domain of cryptosystems, the latter being often based on LCA over (Z/mZ)n with n>1. As a matter of facts, since cryptosystems have to satisfy the so-called confusion and diffusion properties (which are ensured if the involved LCA is chaotic) our algorithm turns out to be an important tool for building chaotic LCA over (Z/mZ)n and, hence, for improving the existing methods based on them.

Abstract Cellular Automata have successfully been successfully applied to the modeling and simulation of pedestrian and crowd dynamics. In particular, the investigated scenarios have often been focused on the evaluation of medium–high population density situations, in which the motivation of pedestrians to reach a certain location overcomes their tendency to naturally respect proxemic distances. The global COVID-19 outbreak, though, has shown that sometimes it is crucial to contemplate how proxemic tendencies are emphasized and amplified by the affective state of the individuals involved in the scenario, representing an important factor to take into consideration when investigating the behaviour of a crowd. In this paper we present a research effort aimed at integrating results of quantitative analyses regarding the effects of affective states on the perception of distances maintained by different types of pedestrians with the modeling of pedestrian movement choices in a cellular automata framework.

Let $\mathbb{K}$ be a finite commutative ring, and let $\mathbb{L}$ be a commutative $\mathbb{K}$-algebra. Let $A$ and $B$ be two $n \times n$-matrices over $\mathbb{L}$ that have the same characteristic polynomial. The main result of this paper states that the set $\left\{ A^0,A^1,A^2,\ldots\right\}$ is finite if and only if the set $\left\{ B^0,B^1,B^2,\ldots\right\}$ is finite. We apply this result to Cellular Automata (CA). Indeed, it gives a complete and easy-to-check characterization of sensitivity to initial conditions and equicontinuity for linear CA over the alphabet $\mathbb{K}^n$ for $\mathbb{K} = \mathbb{Z}/m\mathbb{Z}$ i.e., CA in which the local rule is defined by $n\times n$-matrices with elements in $\mathbb{Z}/m\mathbb{Z}$. To prove our main result, we derive an integrality criterion for matrices that is likely of independent interest. Namely, let $\mathbb{K}$ be any commutative ring (not necessarily finite), and let $\mathbb{L}$ be a commutative $\mathbb{K}$-algebra. Consider any $n \times n$-matrix $A$ over $\mathbb{L}$. Then, $A \in \mathbb{L}^{n \times n}$ is integral over $\mathbb{K}$ (that is, there exists a monic polynomial $f \in \mathbb{K}\left[t\right]$ satisfying $f\left(A\right) = 0$) if and only if all coefficients of the characteristic polynomial of $A$ are integral over $\mathbb{K}$. The proof of this fact relies on a strategic use of exterior powers (a trick pioneered by Gert Almkvist). Furthermore, we extend the decidability result concerning sensitivity and equicontinuity to the wider class of additive CA over a finite abelian group. For such CA, we also prove the decidability of injectivity, surjectivity, topological transitivity and all the properties (as, for instance, ergodicity) that are equivalent to the latter.

This special issue is dedicated to Giancarlo Mauri on the occasion of his 70th birthday.Giancarlo is a well-known prolific

Abstract We continue the study of asynchrony immunity in cellular automata (CA), which can be considered as a generalization of correlation immunity in the case of vectorial Boolean functions. The property could have applications as a countermeasure for side-channel attacks in CA-based cryptographic primitives, such as S-boxes and pseudorandom number generators. We first give some theoretical results on the properties that a CA rule must satisfy in order to meet asynchrony immunity, like central permutivity. Next, we perform an exhaustive search of all asynchrony immune CA rules of neighborhood size up to 5, leveraging on the discovered theoretical properties to greatly reduce the size of the search space.

We study the dynamical behavior of D-dimensional (D >= 1) additive cellular automata where the alphabet is any finite abelian group. This class of discrete time dynamical systems is a generalization of the systems extensively studied by many authors among which one may list [Masanobu Ito et al., 1983; Giovanni Manzini and Luciano Margara, 1999; Giovanni Manzini and Luciano Margara, 1999; Jarkko Kari, 2000; Gianpiero Cattaneo et al., 2000; Gianpiero Cattaneo et al., 2004]. Our main contribution is the proof that topologically transitive additive cellular automata are ergodic. This result represents a solid bridge between the world of measure theory and that of topology theory and greatly extends previous results obtained in [Gianpiero Cattaneo et al., 2000; Giovanni Manzini and Luciano Margara, 1999] for linear CA over Z_m i.e. additive CA in which the alphabet is the cyclic group Z_m and the local rules are linear combinations with coefficients in Z_m. In our scenario, the alphabet is any finite abelian group and the global rule is any additive map. This class of CA strictly contains the class of linear CA over Z_m^n, i.e. , with the local rule defined by n x n matrices with elements in Z_m which, in turn, strictly contains the class of linear CA over Z_m. In order to further emphasize that finite abelian groups are more expressive than Z_m we prove that, contrary to what happens in Z_m, there exist additive CA over suitable finite abelian groups which are roots (with arbitrarily large indices) of the shift map. As a consequence of our results, we have that, for additive CA, ergodic mixing, weak ergodic mixing, ergodicity, topological mixing, weak topological mixing, topological total transitivity and topological transitivity are all equivalent properties. As a corollary, we have that invertible transitive additive CA are isomorphic to Bernoulli shifts. Finally, we provide a first characterization of strong transitivity for additive CA which we suspect it might be true also for the general case.

This issue contains seven papers presented during the "Third Symposium on Cellular Automata-Journes Automates Cellulaires" (JAC 2012), held in La Marana, Corsica (France) in the period September 19th-21th

We investigate the relationships between dynamical complexity and the set of periodic configurations of surjective Cellular Automata. We focus on the set of strictly temporally periodic configurations, i.e., the set of those configurations which are

This special issue of Fundamenta Informaticae is devoted to Gianpiero (Gipo) Cattaneo, in occasion of his retirement and in celebration of his 70th birthday in September 2012. It covers three areas investigated by Gianpiero's research: cellular automata and discrete models, quantum computing and rough sets. The authors of the contributions are friends, pupils and colleagues of Gianpiero from different research

We enlighten the differences between one-dimensional and two-dimensional cellular automata by considering both the dynamical and decidability aspects. We also show a canonical representation theorem for the slicing constructions, a tool allowing to g

This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are “universal”, i.e., allowing a (specific family of) ACA to simulate any Turing machine on any input. We also consider the computational cost of such simulations. Finally, we deal with ACA equipped with peculiar updating sequences, namely those generated by random walks.