Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over \(\mathbb{Z}_p\). (English) Zbl 1535.68145
Summary: The property of reversibility is quite meaningful for the classic theoreticabl computer science model, cellular automata. This paper focuses on the reversibility of general one-dimensional (1D) linear cellular automata (LCA), under null boundary conditions over the finite field \(\mathbb{Z}_p\). Although the existing approaches have split the reversibility challenge into two sub-problems: calculate the period of reversibility first, then verify the reversibility in a period, they are still exponential in the size of the CA’s neighborhood. In this paper, we use two efficient algorithms with polynomial complexity to tackle these two challenges, making it possible to solve large-scale reversible LCA, which substantially enlarge its applicability. Finally, we provide an interesting perspective to inversely generate a 1D LCA from a given period of reversibility.
MSC:
| 68Q80 | Cellular automata (computational aspects) |
References:
| [1] | Acerbi, L.; Dennunzio, A.; Formenti, E., Conservation of some dynamical properties for operations on cellular automata, Theor. Comput. Sci., 410, 3685-3693 (2009) · Zbl 1171.68022 |
| [2] | Akin, H.; Sah, F.; Siap, I., On 1D reversible cellular automata with reflective boundary over the prime field of order p, Int. J. Mod. Phys. C, 23, 1, 1-13 (2012) · Zbl 1275.68098 |
| [3] | Alvarez, G.; Encinas, L. H.; del Rey, A. M., A multisecret sharing scheme for color images based on cellular automata, Inf. Sci., 178, 4382-4395 (2008) · Zbl 1231.94058 |
| [4] | Berlekamp, E., Factoring polynomials over finite fields, Bell Syst. Technical J., 46, 8, 1853-1859 (1967) · Zbl 0166.04901 |
| [5] | Berlekamp, E., Algebraic coding theory (2015), World Scientific: World Scientific New Jersey · Zbl 1320.94001 |
| [6] | Cantor, D. G.; Zassenhaus, H., A new algorithm for factoring polynomials over finite fields, Math. Comput., 587-592 (1981) · Zbl 0493.12024 |
| [7] | Cattaneo, G.; Dennunzio, A.; Margara, L., Solution of some conjectures about topological properties of linear cellular automata, Theor. Comput. Sci., 325, 249-271 (2004) · Zbl 1071.68066 |
| [8] | Chang, C.; Su, J., Reversibility of linear cellular automata on Cayley trees with periodic boundary condition, Taiwan. J. Math., 21, 6, 1335-1353 (2017) · Zbl 1432.37023 |
| [9] | Chang, C.; Su, J.; Akín, H.; Şah, F., Reversibility Problem of Multidimensional Finite Cellular Automata, J. Stat. Phys., 168, 1, 208-231 (2017) · Zbl 1457.37015 |
| [10] | Cinkir, Z.; Hasan, A.; Siap, I., Reversibility of 1D Cellular Automata with Periodic Boundary over Finite Fields \(\mathbb{Z}_p\), J. Stat. Phys., 143, 4, 807-823 (2011) · Zbl 1219.68119 |
| [11] | del Rey, A. M.; Sánchez, G. R., On the reversibility of 150 Wolfram cellular automata, Int. J. Mod. Phys. C, 17, 7, 975-983 (2006) · Zbl 1102.68506 |
| [12] | del Rey, A. M.; Sánchez, G. R., Reversibility of a Symmetric Linear Cellular Automata, Int. J. Mod. Phys. C, 20, 7, 1081-1086 (2009) · Zbl 1175.37020 |
| [13] | del Rey, A. M.; Sánchez, G. R., Reversibility of linear cellular automata, Appl. Math. Comput., 217, 21, 8360-8366 (2011) · Zbl 1219.68120 |
| [14] | del Rey, A. M., A note on the reversibility of elementary cellular automaton 150 with periodic boundary conditions, Rom. J. Inf. Sci. Tech., 16, 4, 365-372 (2013) |
| [15] | del Rey, A. M.; Sánchez, G. R., On the invertible cellular automata 150 over \(F_p\), Appl. Math. Comput., 219, 10, 5427-5432 (2013) · Zbl 1290.68092 |
| [16] | Dennunzio, A.; Di Lena, P.; Formenti, E.; Margara, L., On the directional dynamics of additive cellular automata, Theor. Comput. Sci., 410, 4823-4833 (2009) · Zbl 1180.68183 |
| [17] | Dennunzio, A.; Formenti, E.; Provillard, J., Non-uniform cellular automata: Classes, dynamics, and decidability, Inform. Comput., 215, 32-46 (2012) · Zbl 1260.68249 |
| [18] | Dennunzio, A.; Formenti, E.; Provillard, J., Local rule distributions, language complexity and non-uniform cellular automata, Theor. Comput. Sci., 504, 38-51 (2013) · Zbl 1297.68176 |
| [19] | Dennunzio, A.; Formenti, E.; Provillard, J., Three research directions in non-uniform cellular automata, Theor. Comput. Sci., 559, 73-90 (2014) · Zbl 1360.68611 |
| [20] | Dennunzio, A.; Formenti, E.; Weiss, M., Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues, Theor. Comput. Sci., 516, 40-59 (2014) · Zbl 1360.68612 |
| [21] | Dennunzio, A.; Formenti, E.; Manzoni, L.; Margara, L.; Porreca, A. E., On the dynamical behaviour of linear higher-order cellular automata and its decidability, Inf. Sci., 486, 73-87 (2019) · Zbl 1456.37019 |
| [22] | Dennunzio, A.; Formenti, E.; Grinberg, D.; Margara, L., Chaos and ergodicity are decidable for linear cellular automata over \(( \mathbb{Z} / m \mathbb{Z} )^n\), Inf. Sci., 539, 136-144 (2020) · Zbl 1483.37022 |
| [23] | Dennunzio, A.; Formenti, E.; Grinberg, D.; Margara, L., Dynamical behavior of additive cellular automata over finite abelian groups, Theor. Comput. Sci., 843, 45-56 (2020) · Zbl 1464.37021 |
| [24] | Dennunzio, A.; Formenti, E.; Grinberg, D.; Margara, L., 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 |
| [25] | Dennunzio, A.; Formenti, E.; Grinberg, D.; Margara, L., An efficiently computable characterization of stability and instability for linear cellular automata, J. Comput. Syst. Sci., 122, 63-71 (2021) · Zbl 1527.68136 |
| [26] | Encinas, L. H.; del Rey, A. M., Inverse rules of ECA with rule number 150, Appl. Math. Comput., 189, 2, 1782-1786 (2007) · Zbl 1123.68075 |
| [27] | Itô, M.; Ôsato, N.; Nasu, M., Linear Cellular Automata over \(\mathbb{Z}_m\), J. Comput. Syst. Sci., 27, 125-140 (1983) · Zbl 0566.68047 |
| [28] | Kari, J., Reversibility of 2D cellular automata is undecidable, Physica D, 45, 1-3, 379-385 (1990) · Zbl 0729.68058 |
| [29] | Kari, J., Cryptosystems based on reversible cellular automata, Manuscript (1992) |
| [30] | Kari, J., Theory of cellular automata: A survey, Theor. Comput. Sci., 334, 1-3, 3-33 (2005) · Zbl 1080.68070 |
| [31] | Manzini, G.; Margara, L., A complete and efficiently computable topological classification of D-dimensional linear cellular automata, Theor. Comput. Sci., 221, 157-177 (1999) · Zbl 0930.68090 |
| [32] | R.W. Marsh, Table of irreducible polynomials over GF(2) through degree 19, Office of Technical Services, US Department of Commerce, 1957 |
| [33] | Nobe, A.; Yura, F., On reversibility of cellular automata with periodic boundary conditions, J. Phys. A-Math. Gen., 37, 22, 5789-5804 (2004) · Zbl 1052.81026 |
| [34] | Sah, F.; Siap, I.; Akin, H., Characterization of Three Dimensional Cellular Automata over Z(m)), AIP Conference Proceedings, 1470, 138-141 (Aug. 2012) |
| [35] | Sarkar, P.; Barua, R., The set of reversible 90/150 cellular automata is regular, Discret. Appl. Math., 84, 1-3, 199-213 (1998) · Zbl 0902.68134 |
| [36] | Seck-Tuoh-Mora, J. C.; Martinez, G. J.; Alonso-Sanz, R.; Hernandez-Romero, N., Invertible behavior in elementary cellular automata with memory, Inf. Sci., 199, 1, 125-132 (2012) · Zbl 1248.68345 |
| [37] | Seck-Tuoh-Mora, J. C.; Medina-Marin, J.; Hernandez-Romero, N.; Martinez, G. J.; Barragan-Vite, I., Welch sets for random generation and representation of reversible one-dimensional cellular automata, Inf. Sci., 382-383, 81-95 (2017) · Zbl 1429.68144 |
| [38] | Seck-Tuoh-Mora, J. C.; Martínez, G. J., Graphs Related to Reversibility and Complexity in Cellular Automata, Cellular Automata: A Volume in the Encyclopedia of Complexity and Systems Science, Second Edition, Springer, 479-492 (2018) · Zbl 1484.37027 |
| [39] | Shoup, V., New algorithms for finding irreducible polynomials over finite fields, Math. Comput., 54, 189, 435-447 (1990) · Zbl 0712.11077 |
| [40] | Siap, I.; Akin, H.; Sah, F., Garden of eden configurations for 2-D cellular automata with rule 2460N, Inf. Sci., 180, 18, 3562-3571 (2010) · Zbl 1206.68205 |
| [41] | Siap, I.; Akin, H.; Uğuz, S., Structure and reversibility of 2D hexagonal cellular automata, Comput. Math. Appl., 62, 11, 4161-4169 (2011) · Zbl 1236.68191 |
| [42] | Siap, I.; Akin, H.; Koroglu, M. E., Reversible Cellular Automata with Penta-Cyclic Rule and ECCs, Int. J. Mod. Phys. C, 23, 10, 1-13 (2012) |
| [43] | Sutner, K., σ-Automata and Chebyshev-polynomials, Theor. Comput. Sci., 230, 1-2, 49-73 (2000) · Zbl 0947.68540 |
| [44] | Uğuz, S.; Akin, H.; Siap, I., Reversibility Algorithms for 3-State Hexagonal Cellular Automata with Periodic Boundaries, Int. J. Bifurcat. Chaos, 23, 6, 1-15 (2013) · Zbl 1272.37010 |
| [45] | Gathen, J. V.Z.; Panario, D., Factoring polynomials over finite fields: A survey, J. Symb. Comput., 31, 1-2, 3-17 (2001) · Zbl 0969.11041 |
| [46] | Wang, X.; Luan, D., A novel image encryption algorithm using chaos and reversible cellular automata, Commun. Nonlinear Sci. Numer. Simul., 18, 11, 3075-3085 (2013) · Zbl 1329.94081 |
| [47] | Wolfram, S., Cellular automata and complexity: collected papers (2018), CRC Press |
| [48] | Yang, B.; Wang, C.; Xiang, A., Reversibility of general 1D linear cellular automata over the binary field \(\mathbb{Z}_2\) under null boundary conditions, Inf. Sci., 324, 1, 23-31 (2015) · Zbl 1390.68451 |
| [49] | C. Zhang, Q. Peng and Y. Li, Encryption based on reversible cellular automata, IEEE 2002 International Conference on Communications, Circuits and Systems and West Sino Expositions, 2(2002), 1223-1226. |
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.
