Decision algorithms for reversibility of 1D cellular automata under reflective boundary conditions. (English) Zbl 07902298
Summary: Reversibility is one of the most significant properties of cellular automata (CA). In this paper, we focus on the reversibility of one-dimensional finite CA under reflective boundary conditions (RBC). We present two algorithms for deciding the reversibility of one-dimensional CA under RBC. Both algorithms work for not only linear rules but also non-linear rules. The first algorithm is to determine what we call the “strict reversibility” of CA. The second algorithm is to compute what we call the “reversibility function” of CA. Reversibility functions are proved to be periodic. Based on the algorithms, we list some experiment results of one-dimensional CA under RBC and analyse some features of this family of CA.
MSC:
| 68Qxx | Theory of computing |
Keywords:
cellular automata; nonlinear rules; reversibility; reflective boundary conditions; one-dimensionalReferences:
| [1] | Abdo, A.; Lian, S.; Ismail, I. A.; Amin, M.; Diab, H., A cryptosystem based on elementary cellular automata, Commun. Nonlinear Sci. Numer. Simul., 18, 136-147, 2013 · Zbl 1277.94011 |
| [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, Article 1250004 pp., 2012 · Zbl 1275.68098 |
| [3] | Amoroso, S.; Patt, Y. N., Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures, J. Comput. Syst. Sci., 6, 448-464, 1972 · Zbl 0263.94019 |
| [4] | Bruckner, L. K., On the garden-of-eden problem for one-dimensional cellular automata, Acta Cybern., 4, 259-262, 1979 · Zbl 0422.68021 |
| [5] | Cappellari, L.; Milani, S.; Cruz-Reyes, C.; Calvagno, G., Resolution scalable image coding with reversible cellular automata, IEEE Trans. Image Process., 20, 1461-1468, 2010 · Zbl 1372.94031 |
| [6] | Chaudhuri, P. P.; Chowdhury, D. R.; Nandi, S.; Chattopadhyay, S., Additive Cellular Automata, Theory and Applications, vol. 1. volume 43, 1997, John Wiley & Sons · Zbl 0944.68133 |
| [7] | Cinkir, Z.; Akin, H.; Siap, I., Reversibility of 1d cellular automata with periodic boundary over finite fields \(\mathbb{Z}_p\), J. Stat. Phys., 143, 807-823, 2011 · Zbl 1219.68119 |
| [8] | Du, X.; Wang, C.; Wang, T.; Gao, Z., Efficient methods with polynomial complexity to determine the reversibility of general 1d linear cellular automata over zp, Inf. Sci., 594, 163-176, 2022 · Zbl 1535.68145 |
| [9] | Gardner, M., Mathematical games, Sci. Am., 222, 132-140, 1970 |
| [10] | Isinkaralar, O.; Varol, C., A cellular automata-based approach for spatio-temporal modeling of the city center as a complex system: the case of kastamonu, Türkiye, Cities, 132, Article 104073 pp., 2023 |
| [11] | Kazmi, N.; Hossain, M. A.; Phillips, R. M., A hybrid cellular automaton model of solid tumor growth and bioreductive drug transport, IEEE/ACM Trans. Comput. Biol. Bioinform., 9, 1595-1606, 2012 |
| [12] | Kippenberger, S.; Bernd, A.; Thaçi, D.; Kaufmann, R.; Meissner, M., Modeling pattern formation in skin diseases by a cellular automaton, J. Invest. Dermatol., 133, 567, 2013 |
| [13] | Li, Y.; Chen, M.; Dou, Z.; Zheng, X.; Cheng, Y.; Mebarki, A., A review of cellular automata models for crowd evacuation, Phys. A, Stat. Mech. Appl., 526, Article 120752 pp., 2019 |
| [14] | Maerivoet, S.; De Moor, B., Cellular automata models of road traffic, Phys. Rep., 419, 1-64, 2005 |
| [15] | Mastorakos, E.; Gkantonas, S.; Efstathiou, G.; Giusti, A., A hybrid stochastic Lagrangian-cellular automata framework for modelling fire propagation in inhomogeneous terrains, Proc. Combust. Inst., 39, 3853-3862, 2023 |
| [16] | Moore, E. F., Machine models of self-reproduction, (Proceedings of Symposia in Applied Mathematics, 1962, American Mathematical Society: American Mathematical Society New York), 17-33 · Zbl 0126.32408 |
| [17] | Moreira, J.; Deutsch, A., Cellular automaton models of tumor development: a critical review, Adv. Complex Syst., 5, 247-267, 2002 · Zbl 1020.92016 |
| [18] | Neumann, J. V., Theory of self-reproducing automata. Edited by Arthur W. Burks, 1966 |
| [19] | del Rey, A. M., A note on the reversibility of elementary cellular automaton 150 with periodic boundary conditions, Rom. J. Inf. Sci. Technol., 16, 365-372, 2013 |
| [20] | del Rey, A. M., A note on the reversibility of the elementary cellular automaton with rule number 90, Rev. Unión Mat. Argent., 56, 2015 · Zbl 1336.68171 |
| [21] | del Rey, A. M.; Sánchez, G. R., On the reversibility of 150 wolfram cellular automata, Int. J. Mod. Phys. C, 17, 975-983, 2006 · Zbl 1102.68506 |
| [22] | del Rey, A. M.; Sánchez, G. R., Reversible elementary cellular automaton with rule number 150 and periodic boundary conditions over \(\mathbb{F}_p\), Int. J. Mod. Phys. C, 26, Article 1550120 pp., 2015 |
| [23] | Sarkar, P.; Barua, R., The set of reversible 90/150 cellular automata is regular, Discrete Appl. Math., 84, 199-213, 1998 · Zbl 0902.68134 |
| [24] | Sutner, K., De Bruijn graphs and linear cellular automata, Complex Syst., 5, 19-30, 1991 · Zbl 0764.68100 |
| [25] | Tong, X.; Feng, Y., A review of assessment methods for cellular automata models of land-use change and urban growth, Int. J. Geogr. Inf. Sci., 34, 866-898, 2020 |
| [26] | Viriyasitavat, W.; Bai, F.; Tonguz, O. K., Dynamics of network connectivity in urban vehicular networks, IEEE J. Sel. Areas Commun., 29, 515-533, 2011 |
| [27] | Wang, Y.; Zhang, L.; Ma, J.; Liu, L.; You, D.; Zhang, L., Combining building and behavior models for evacuation planning, IEEE Comput. Graph. Appl., 31, 42-55, 2010 |
| [28] | Wolfram, S., A New Kind of Science, vol. 5, 2002, Wolfram Media Champaign: Wolfram Media Champaign IL · Zbl 1022.68084 |
| [29] | Yang, B.; Wang, C.; Xiang, A., Reversibility of general 1d linear cellular automata over the binary field z2 under null boundary conditions, Inf. Sci., 324, 23-31, 2015 · Zbl 1390.68451 |
| [30] | Zeng, J.; Wang, C., A novel hyperchaotic image encryption system based on particle swarm optimization algorithm and cellular automata, Secur. Commun. Netw., 2021, 1-15, 2021 |
| [31] | Zhang, X.; Wang, C.; Zhong, S.; Yao, Q., Image encryption scheme based on balanced two-dimensional cellular automata, Math. Probl. Eng., 2013, 2013 · Zbl 1299.94035 |
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.
