×

Set of periods of additive cellular automata. (English) Zbl 1087.68063

Summary: It is shown that the set of periods of any additive cellular automata \(F\), where the addition is done modulo a prime \(p\), can be determined using some simple conditions on the coefficients in the linear expression of \(F\). In particular, we establish that the set of periods has only four possibilities: \(\{1,m\}\) for some \(m\) where \(1\leq m<p\), \(\mathbb{N} \setminus\{p^m:m\in\mathbb{N}\}\), \(\mathbb{N}\setminus\{2 p^m:m \in\mathbb{N}\cup \{0\}\}\) or the whole set \(\mathbb{N}=\{1,2,3,\dots\}\). Using our results, the set of periods of any additive cellular automata, where the addition is done modulo a square-free positive integer, is easily obtained.

MSC:

68Q80 Cellular automata (computational aspects)
Full Text: DOI

References:

[1] L.S. Block, W.A. Coppel, Dynamics in one dimension, Lecture Notes in Mathematics, Springer, Berlin, vol. 1513, 1992.; L.S. Block, W.A. Coppel, Dynamics in one dimension, Lecture Notes in Mathematics, Springer, Berlin, vol. 1513, 1992. · Zbl 0746.58007
[2] Favati, P.; Lotti, G.; Margara, L., Additive one-dimensional cellular automata are chaotic according to Devaney’s definition of chaos, Theoret. Comput. Sci., 174, 1-2, 157-170 (1997) · Zbl 0902.68133
[3] P. Kurka, Topological Dynamics of cellular automata, Codes, Systems, and Graphical Models, IMA, Mathematics and Its Applications, vol. 123, Springer, Berlin, 2001, pp. 447-486.; P. Kurka, Topological Dynamics of cellular automata, Codes, Systems, and Graphical Models, IMA, Mathematics and Its Applications, vol. 123, Springer, Berlin, 2001, pp. 447-486. · Zbl 1198.37019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.