×

An efficiently computable characterization of stability and instability for linear cellular automata. (English) Zbl 1527.68136

Summary: We provide an efficiently computable characterization of two important properties describing stable and unstable complex behaviours as equicontinuity and sensitivity to the initial conditions for one-dimensional linear cellular automata (LCA) over \((\mathbb{Z}/m \mathbb{Z})^n\). We stress that the setting of LCA over \((\mathbb{Z}/m\mathbb{Z})^n\) with \(n>1\) is more expressive, it gives rise to much more complex dynamics, and it is more difficult to deal with than the already investigated case \(n=1\). Indeed, in order to get our result we need to prove a nontrivial result of abstract algebra: if \(\mathbb{K}\) is any finite commutative ring and \(\mathbb{L}\) is any \(\mathbb{K}\)-algebra, then for every pair \(A, B\) of \(n\times n\) matrices over \(\mathbb{L}\) having the same characteristic polynomial, it holds that the set \(\{A^0,A^1,A^2,\dots\}\) is finite if and only if the set \(\{B^0,B^1,B^2,\dots\}\) is finite too.

MSC:

68Q80 Cellular automata (computational aspects)
37B15 Dynamical aspects of cellular automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aluffi, P., Algebra: Chapter 0, Graduate Studies in Mathematics (2009), American Mathematical Society · Zbl 1179.00001
[2] Anghelescu, Petre; Ionita, Silviu; Sofron, Emil, Block encryption using hybrid additive cellular automata, (König, Andreas; Köppen, Mario; Kasabov, Nikola K.; Abraham, Ajith, 7th International Conference on Hybrid Intelligent Systems. 7th International Conference on Hybrid Intelligent Systems, HIS 2007, Kaiserslautern, Germany, September 17-19, 2007 (2007), IEEE Computer Society), 132-137, available from
[3] Béaur, Pierre; Kari, Jarkko, Decidability in group shifts and group cellular automata, (Esparza, Javier; Král’, Daniel, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020. 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, Prague, Czech Republic, August 24-28, 2020. 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020. 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, Prague, Czech Republic, August 24-28, 2020, LIPIcs, vol. 170 (2020), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), Article 12 pp.
[4] Bernardi, Vincent; Durand, Bruno; Formenti, Enrico; Kari, Jarkko, A new dimension sensitive property for cellular automata, (Fiala, Jirí; Koubek, Václav; Kratochvíl, Jan, Proceedings of Mathematical Foundations of Computer Science 2004, 29th International Symposium. Proceedings of Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings of Mathematical Foundations of Computer Science 2004, 29th International Symposium. Proceedings of Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Lecture Notes in Computer Science, vol. 3153 (2004), Springer), 416-426 · Zbl 1096.68098
[5] Bourbaki, N., Elements of Mathematics: Commutative Algebra, Actualités Scientifiques et Industrielles, vol. 8 (1972), Addison-Wesley · Zbl 0279.13001
[6] Le Bruyn, Lieven; Van den Bergh, Michel, Algebraic properties of linear cellular automata, Linear Algebra Appl., 157, 217-234 (1991) · Zbl 0790.68083
[7] Cattaneo, Gianpiero; Dennunzio, Alberto; Margara, Luciano, Solution of some conjectures about topological properties of linear cellular automata, Theor. Comput. Sci., 325, 2, 249-271 (2004) · Zbl 1071.68066
[8] Cattaneo, Gianpiero; Formenti, Enrico; Manzini, Giovanni; Margara, Luciano, Ergodicity, transitivity, and regularity for linear cellular automata over \(\mathbb{Z}_m\), Theor. Comput. Sci., 233, 1-2, 147-164 (2000) · Zbl 0953.37002
[9] Chambert-Loir, Antoine, (Mostly) Commutative Algebra (2014), Springer · Zbl 1477.13001
[10] Dennunzio, Alberto; Formenti, Enrico; Grinberg, Darij; Margara, Luciano, Chaos and ergodicity are decidable for linear cellular automata over \(( \mathbb{Z} / m \mathbb{Z} )^n\), Inf. Sci., 539, 136-144 (2020) · Zbl 1464.37021
[11] Dennunzio, Alberto; Formenti, Enrico; Grinberg, Darij; Margara, Luciano, Dynamical behavior of additive cellular automata over finite abelian groups, Theor. Comput. Sci., 843, 45-56 (2020) · Zbl 1464.37021
[12] Dennunzio, Alberto; Formenti, Enrico; Grinberg, Darij; Margara, Luciano, From linear to additive cellular automata, (Czumaj, Artur; Dawar, Anuj; Merelli, Emanuela, 47th International Colloquium on Automata, Languages, and Programming. 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference). 47th International Colloquium on Automata, Languages, and Programming. 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), LIPIcs, vol. 168 (2020), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), Article 125 pp. · Zbl 1464.37021
[13] Dennunzio, Alberto; Formenti, Enrico; Grinberg, Darij; Margara, Luciano, Decidable characterizations of dynamical properties for additive cellular automata over a finite abelian group with applications to data encryption, Inf. Sci., 563, 183-195 (2021) · Zbl 1527.68137
[14] Dennunzio, Alberto; Formenti, Enrico; Manzoni, Luca; Margara, Luciano; Porreca, Antonio E., On the dynamical behaviour of linear higher-order cellular automata and its decidability, Inf. Sci., 486, 73-87 (2019) · Zbl 1456.37019
[15] Dennunzio, Alberto; Formenti, Enrico; Provillard, Julien, Non-uniform cellular automata: classes, dynamics, and decidability, Inf. Comput., 215, 32-46 (2012) · Zbl 1260.68249
[16] Dennunzio, Alberto; Formenti, Enrico; Provillard, Julien, Local rule distributions, language complexity and non-uniform cellular automata, Theor. Comput. Sci., 504, 38-51 (2013) · Zbl 1297.68176
[17] Dennunzio, Alberto; Formenti, Enrico; Provillard, Julien, Three research directions in non-uniform cellular automata, Theor. Comput. Sci., 559, 73-90 (2014) · Zbl 1360.68611
[18] Durand, Bruno; Formenti, Enrico; Varouchas, Georges, On undecidability of equicontinuity classification for cellular automata, (Discrete Models for Complex Systems. Discrete Models for Complex Systems, DMCS’03, Lyon, France, June 16-19, 2003. Discrete Models for Complex Systems. Discrete Models for Complex Systems, DMCS’03, Lyon, France, June 16-19, 2003, Discrete Mathematics and Theoretical Computer Science Proceedings, vol. AB (2003), DMTCS), 117-128 · Zbl 1073.68686
[19] Pin, Jean Éric, Mathematical foundations of automata theory (2020), available from
[20] Grinberg, Darij, Integrality over ideal semifiltrations (2019), available from
[21] Guillon, Pierre; Richard, Gaétan, Revisiting the Rice theorem of cellular automata, (Marion, Jean-Yves; Schwentick, Thomas, 27th International Symposium on Theoretical Aspects of Computer Science. 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, Nancy, France, March 4-6, 2010. 27th International Symposium on Theoretical Aspects of Computer Science. 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, Nancy, France, March 4-6, 2010, LIPIcs, vol. 5 (2010), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 441-452 · Zbl 1230.68152
[22] Huneke, C.; Swanson, I., Integral Closure of Ideals, Rings, and Modules, London Mathematical Society Lecture Notes (2014), Cambridge University Press
[23] Ito, Masanobu; Osato, Nobuyasu; Nasu, Masakazu, Linear cellular automata over \(\mathbb{Z}_m\), Sov. J. Comput. Syst. Sci., 27, 125-140 (1983) · Zbl 0566.68047
[24] Kari, Jarkko, Rice’s theorem for the limit sets of cellular automata, Theor. Comput. Sci., 127, 2, 229-254 (1994) · Zbl 0824.68078
[25] Kari, Jarkko, Linear cellular automata with multiple state variables, (Reichel, Horst; Tison, Sophie, STACS 2000. STACS 2000, LNCS, vol. 1770 (2000), Springer-Verlag), 110-121 · Zbl 0959.68085
[26] Kleiman, S.; Altman, A., A Term of Commutative Algebra. Worldwide Center of Mathematics (2013), LLC
[27] Manzini, Giovanni; Margara, Luciano, Attractors of linear cellular automata, J. Comput. Syst. Sci., 58, 3, 597-610 (1999) · Zbl 0939.68077
[28] Manzini, Giovanni; Margara, Luciano, A complete and efficiently computable topological classification of d-dimensional linear cellular automata over \(\mathbb{Z}_m\), Theor. Comput. Sci., 221, 1-2, 157-177 (1999) · Zbl 0930.68090
[29] Fraile Rubio, C.; Hernández Encinas, Luis; Hoya White, S.; Martín del Rey, Ángel; Sánchez, Gerardo Rodríguez, The use of linear hybrid cellular automata as pseudo random bit generators in cryptography, Neural Parallel Sci. Comput., 12, 2, 175-192 (2004) · Zbl 1161.68439
[30] Steinberg, Benjamin, Representation Theory of Finite Monoids (2016), Springer · Zbl 1428.20003
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.