Reversibility of linear cellular automata on Cayley trees with periodic boundary condition. (English) Zbl 1432.37023

Summary: While one-dimensional cellular automata have been well studied, there are relatively few results about multidimensional cellular automata; the investigation of cellular automata defined on Cayley trees constitutes an intermediate class. This paper studies the reversibility of linear cellular automata defined on Cayley trees with periodic boundary condition, where the local rule is given by \(f(x_0,x_1,\ldots,x_d) = b x_0 + c_1 x_1 + \cdots + c_d x_d \pmod{m}\) for some integers \(m,d \geq 2\). The reversibility problem relates to solving a polynomial derived from a recurrence relation, and an explicit formula is revealed; as an example, the complete criteria of the reversibility of linear cellular automata defined on Cayley trees over \(\mathbb{Z}_2\), \(\mathbb{Z}_3\), and some other specific case are addressed. Further, this study achieves a possible approach for determining the reversibility of multidimensional cellular automata, which is known as a undecidable problem.


37B15 Dynamical aspects of cellular automata
68Q80 Cellular automata (computational aspects)
03D35 Undecidability and degrees of sets of sentences
Full Text: DOI arXiv Euclid


[1] N. Aubrun and M.-P. Béal, Sofic tree-shifts, Theory Comput. Syst. 53 (2013), no. 4, 621-644. · Zbl 1293.68195
[2] J.-C. Ban and C.-H. Chang, Tree-shifts: Irreducibility, mixing, and chaos of tree-shifts, Trans. Amer. Math. Soc. (2017), accepted. · Zbl 1379.37024
[3] T. Ceccherini-Silberstein, M. Coornaert, F. Fiorenzi and Z. Šunić, Cellular automata between sofic tree shifts, Theoret. Comput. Sci. 506 (2013), 79-101. · Zbl 1301.68185
[4] C.-H. Chang and H. Chang, On the Bernoulli automorphism of reversible linear cellular automata, Inform. Sci. 345 (2016), 217-225. · Zbl 1400.37016
[5] P. Chattopadhyay, P. P. Choudhury and K. Dihidar, Characterisation of a particular hybrid transformation of two-dimensional cellular automata, Comput. Math. Appl. 38 (1999), no. 5-6, 207-216. · Zbl 0942.68074
[6] Z. Cinkir, H. Akin and \.I. Şiap, Reversibility of \(1D\) cellular automata with periodic boundary over finite fields \(\mb{Z}_p\), J. Stat. Phys. 143 (2011), no. 4, 807-823. · Zbl 1219.68119
[7] K. Dihidar and P. P. Choudhury, Matrix algebraic formulae concerning some exceptional rules of two-dimensional cellular automata, Inform. Sci. 165 (2004), no. 1-2, 91-101. · Zbl 1089.68067
[8] L. H. Encinas and A. M. del Rey, Inverse rules of ECA with rule number 150, Appl. Math. Comput. 189 (2007), no. 2, 1782-1786. · Zbl 1123.68075
[9] A. B. Feldman, Y. B. Chernyak and R. J. Cohen, Wave-front propagation in a discrete model of excitable media, Phys. Rev. E (3) 57 (1998), no. 6, 7025-7040.
[10] G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320-375. · Zbl 0182.56901
[11] M. Itô, N. Ôsato and M. Nasu, Linear cellular automata over \(Z_m\), J. Comput. System Sci. 27 (1983), no. 1, 125-140. · Zbl 0566.68047
[12] J. Kari, Reversibility of \(2D\) cellular automata is undecidable, Phys. D 45 (1990), no. 1-3, 379-385. · Zbl 0729.68058
[13] —-, Reversibility and surjectivity problems of cellular automata, J. Comput. System Sci. 48 (1994), no. 1, 149-182. · Zbl 0802.68090
[14] A. R. Khan, P. P. Choudhury, K. Dihidar and R. Verma, Text compression using two-dimensional cellular automata, Comput. Math. Appl. 37 (1999), no. 6, 115-127. · Zbl 0938.68726
[15] M. E. Köroğlu, \.I. Şiap and H. Akin, The reversibility problem for a family of two-dimensional cellular automata, Turkish J. Math. 40 (2016), no. 3, 665-678. · Zbl 1424.37006
[16] K. Morita, Reversible cellular automata, in Handbook of Natural Computing, 231-257, Springer, Heidelberg, 2012. · Zbl 1283.68230
[17] M. Nasu, The dynamics of expansive invertible onesided cellular automata, Trans. Amer. Math. Soc. 354 (2002), no. 10, 4067-4084. · Zbl 1034.37011
[18] \.I. Şiap, H. Akin and M. E. Köroğlu, Reversible cellular automata with penta-cyclic rule and ECCs, Internat. J. Modern Phys. C 23 (2012), no. 10, 1250066, 13 pp. · JFM 59.0077.06
[19] S. Wolfram, A New Kind of Science, Wolfram Media, Champaign, IL, 2002. · Zbl 1022.68084
[20] B. Yang, C. Wang and A. Xiang, Reversibility of general \(1D\) linear cellular automata over the binary field \(\mb{Z}_2\) under null boundary conditions, Inform. Sci. 324 (2015), 23-31. · Zbl 1390.68451
[21] Y. Zhai, Z. Yi. and P.-M. Deng, On behavior of two-dimensional cellular automata with an exceptional rule, Inform. Sci. 179 (2009), no. 5, 613-622. · Zbl 1170.68025
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.