Reversibility of linear cellular automata with intermediate boundary condition

Chih-Hung Chang; Ya-Chu Yang; Ferhat Şah; Chih-Hung Chang; Ya-Chu Yang; Ferhat Şah

doi:10.3934/math.2024371

AIMS Mathematics

2024, Volume 9, Issue 3: 7645-7661. doi: 10.3934/math.2024371

Previous Article Next Article

Research article Special Issues

Reversibility of linear cellular automata with intermediate boundary condition

1.
Department of Applied Mathematics, National University of Kaohsiung, Kaohsiung 81148, Taiwan, R.O.C
2.
Adiyaman University, Faculty of Economics and Administrative Sciences, Adiyaman 02040, Turkey

Received: 03 December 2023 Revised: 22 January 2024 Accepted: 30 January 2024 Published: 22 February 2024
MSC : 37A35, 37B10

This paper focuses on the reversibility of multidimensional linear cellular automata with an intermediate boundary condition. We begin by addressing the matrix representation of these automata, and the question of reversibility boils down to the invertibility of this matrix representation. We introduce a decomposition method that factorizes the matrix representation into a Kronecker sum of significantly smaller matrices. The invertibility of the matrix hinges on determining whether zero can be expressed as the sum of eigenvalues of these smaller matrices, which happen to be tridiagonal Toeplitz matrices. Notably, each of these smaller matrices represents a one-dimensional cellular automaton. Leveraging the rich body of research on the eigenvalue problem of Toeplitz matrices, our result provides an efficient algorithm for addressing the reversibility problem. As an application, we show that there is no reversible nontrivial linear cellular automaton over $ \mathbb{Z}_2 $.
- cellular automata,
- reversibility,
- intermediate boundary condition,
- Kronecker sum,
- Toeplitz matrix
Citation: Chih-Hung Chang, Ya-Chu Yang, Ferhat Şah. Reversibility of linear cellular automata with intermediate boundary condition[J]. AIMS Mathematics, 2024, 9(3): 7645-7661. doi: 10.3934/math.2024371

Related Papers:

Abstract

This paper focuses on the reversibility of multidimensional linear cellular automata with an intermediate boundary condition. We begin by addressing the matrix representation of these automata, and the question of reversibility boils down to the invertibility of this matrix representation. We introduce a decomposition method that factorizes the matrix representation into a Kronecker sum of significantly smaller matrices. The invertibility of the matrix hinges on determining whether zero can be expressed as the sum of eigenvalues of these smaller matrices, which happen to be tridiagonal Toeplitz matrices. Notably, each of these smaller matrices represents a one-dimensional cellular automaton. Leveraging the rich body of research on the eigenvalue problem of Toeplitz matrices, our result provides an efficient algorithm for addressing the reversibility problem. As an application, we show that there is no reversible nontrivial linear cellular automaton over $ \mathbb{Z}_2 $.

References

[1]	H. Akın, F. Sah, I. Siap, On 1D reversible cellular automata with reflective boundary over the prime field of order p, Int. J. Mod. Phys. C, 23 (2012), 1250004. https://doi.org/10.1142/S0129183111017020 doi: 10.1142/S0129183111017020
[2]	H. Akın, I. Siap, S. Uguzc, One-dimensional cellular automata with reflective boundary conditions and radius three, Acta Phys. Polonica A, 125 (2014), 405–407. https://doi.org/10.12693/APhysPolA.125.405 doi: 10.12693/APhysPolA.125.405
[3]	B. M. Boghosian, Lattice gases and cellular automata, Future Gener. Comp. Sy., 16 (1999), 171–185. https://doi.org/10.1016/S0167-739X(99)00045-X doi: 10.1016/S0167-739X(99)00045-X
[4]	A. Böttcher, S. Grudsky, Spectral properties of banded Toeplitz matrices, Soc. Ind. Appl. Math., 2005. https://doi.org/10.1137/1.9780898717853 doi: 10.1137/1.9780898717853
[5]	C. H. Chang, J. Y. Su, H. Akın, F. Sah, Reversibility problem of multidimensional finite cellular automata, J. Stat. Phys., 168 (2017), 208–231. https://doi.org/10.1007/s10955-017-1799-6 doi: 10.1007/s10955-017-1799-6
[6]	C. H. Chang, Y. C. Yang, Characterization of reversible intermediate boundary cellular automata, J. Stat. Mech.-Theory E., 2020 (2020), 013215. https://doi.org/10.1088/1742-5468/ab5b8f doi: 10.1088/1742-5468/ab5b8f
[7]	R. J. Chen, S. J. Horng, Novel SCAN-CA-based image security system using SCAN and 2-D von Neumann cellular automata, Signal Process.-Image, 25 (2010), 413–426.
[8]	Z. Cinkir, H. Akın, I. Siap, Reversibility of 1D cellular automata with periodic boundary over finite fields $\mathbb{Z}_p$, J. Stat. Phys., 143 (2011), 807–823.
[9]	S. Das, B. K. Sikdar, Characterization of 1-d periodic boundary reversible CA, Electron. Notes Theor. Comput. Sci., 252 (2009), 205–227. https://doi.org/10.1016/j.entcs.2009.09.022 doi: 10.1016/j.entcs.2009.09.022
[10]	L. Gray, A mathematician looks at wolfram's new kind of science, Notices of the AMS, 50 (2003), 200–211.
[11]	J. Kari, Reversibility of 2D cellular automata is undecidable, Physica D, 45 (1990), 386–395.
[12]	J. Kari, Cryptosystems based on reversible cellular automata, Manuscript, August, 1992.
[13]	J. Kari, Reversibility and surjectivity problems of cellular automata, J. Comput. Syst. Sci., 48 (1994), 149–182. https://doi.org/10.1016/S0022-0000(05)80025-X doi: 10.1016/S0022-0000(05)80025-X
[14]	J. Kari, Reversible cellular automata, International Conference on Developments in Language Theory, Springer, 2005, 57–68.
[15]	M. E. Köroğlu, I. Siap, H. Akın, The reversibility problem for a family of two-dimensional cellular automata, Turkish J. Math., 40 (2016), 665–678.
[16]	A. J. Laub, Matrix analysis for scientists and engineers, SIAM, 91 (2005).
[17]	G. Manzini, L. Margara, Invertible linear cellular automata over $\mathbb{Z}_m$: Algorithmic and dynamical aspects, J. Comput. Syst. Sci., 56 (1998), 60–67.
[18]	Z. Mehrnahad, A. Latif, A novel image encryption scheme based on reversible cellular automata and chaos, Int. J. Inf. Technol. Comput. Sci., 11 (2019), 15–23. https://doi.org/10.5815/ijitcs.2019.11.02 doi: 10.5815/ijitcs.2019.11.02
[19]	H. Nishio, Changing the neighborhood of cellular automata, International Conference on Machines, Computations, and Universality, Springer, 2007,255–266.
[20]	A. Popovici, D. Popovici, Cellular automata in image processing, Fifteenth international symposium on mathematical theory of networks and systems, Citeseer, 1 (2002), 1–6.
[21]	B. Ribba, T. Alarcon, K. Marron, P. K. Maini, Z. Agur, The use of hybrid cellular automaton models for improving cancer therapy, Lecture Notes in Computer Science, Springer, 3305 (2004), 444–453.
[22]	P. J. Selvapeter, W. Hordijk, Cellular automata for image noise filtering, 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), IEEE, 2009,193–197.
[23]	P. Sharma, M. Diwakar, N. Lal, Edge detection using moore neighborhood, Int. J. Comput. Appl., 61 (2013), 26–30. https://doi.org/10.5120/9910-4506 doi: 10.5120/9910-4506
[24]	I. Siap, H. Akın, F. Sah, Characterization of two dimensional cellular automata over ternary fields, 348 (2011), 1258–1275.
[25]	I. Siap, H. Akın, S. Uguz, Structure and reversibility of 2-dimensional hexagonal cellular automata, AIP Conference Proceedings, 62 (2011), 4161–4169.
[26]	F. Temiz, F. Sah, H. Akın, Reversibility of a family of 2D cellularautomata hybridized by diamond andcross rules over finite fields and anapplication to visual cryptography, J. Cell. Autom., 14 (2019), 241–262.
[27]	S. Uguz, H. Akın, I. Siap, U. Sahin, On the irreversibility of moore cellular automata over the ternary field and image application, Appl. Math. Model., 40 (2016), 8017–8032. https://doi.org/10.1016/j.apm.2016.04.027 doi: 10.1016/j.apm.2016.04.027
[28]	J. Wang, Periodicity and invertibility of lattice gas cellular automata, 2019.
[29]	X. Wang, D. Luan, A novel image encryption algorithm using chaos and reversible cellular automata, Commun. Nonlinear Sci. Numer. Simul., 18 (2013), 3075–3085. https://doi.org/10.1016/j.cnsns.2013.04.008 doi: 10.1016/j.cnsns.2013.04.008
[30]	S. Wolfram, A new kind of science, Wolfram media Champaign, IL, 2002.
[31]	B. Yang, C. Wang, A. Xiang, Reversibility of general 1D linear cellular automata over the binary field $\mathbb{Z}^2$ under null boundary conditions, Inform. Sci., 324 (2015), 23–31.
[32]	X. Zhang, D. Wang, B. Huang, S. Wang, Z. Zhang, S. Li, et al., A dynamic-static coupling topology optimization method based on hybrid cellular automata, Structures, 50 (2023), 1573–1583. https://doi.org/10.1016/j.istruc.2023.02.120 doi: 10.1016/j.istruc.2023.02.120

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)