Application and Reversibility of Three Dimensional Cellular Automata

Abstract

In this study, we obtain the characteristic matrices of three-dimensional cellular automata under the null boundary condition. We examine the inverse of characteristic matrices. We obtain a recurrence equation to determine under what conditions the matrix is invertible. Thanks to this equation, we can calculate the inverse of large-dimensional matrices. Finally, we give some applications of cellular automata. We find the minimal polynomial of the characteristic matrix. We find the cycle length and transition length of the characteristic matrix with the help of minimal polynomials. We also find the attractive points of the characteristic matrix. Finally, we draw the State Transition diagram with the results we obtained.

Keywords

• Hücresel Dönüşümler
• Karakteristik Matrisler
• Terslenebilirlik

Application and Reversibility of Three Dimensional Cellular Automata

Abstract

Bu çalışmada üç boyutlu hücresel dönüşümlerin karakteristik matrislerini sıfır sınır şartı altında elde ediyoruz. Karakteristik matrislerin tersini inceliyoruz. Matrisin hangi şartlarda tersinin olduğunu belirlemek için rekürans denklem elde ediyoruz. Bu denklem sayesinde büyük boyutlu matrislerin tersini hesaplayabiliriz. Son olarak hücresel dönüşümlerin bazı uygulamalarını veriyoruz. Karakteristik matrisin minimal polinomunu buluyoruz. Minimal polinom yardımıyla karakteristik matrisin devir uzunluğu ve geçiş uzunluğunu buluyoruz. Ayrıca karakteristik matrisin çekici noktalarını buluyoruz. Son olarak elde ettiğimiz sonuçlar ile Durum–Geçiş diyagramını çiziyoruz. Hücresel Dönüşümler, Karakteristik Matrisler, Terslenebilirlik

Keywords

• Cellular Automata
• Characteristic Matrices
• Reversibility

References

1. Von N.J. The theory of self-reproducing automata, (Edited by A. W. Burks) University of Illinois Press, Urbana, 1966.
2. Hedlund G.A. Endomorphisms and automorphisms of full shift dynamical system, Mathematical Systems Theory. 3 320- 375, 1969.
3. Wolfram S. Statistical mechanics of cellular automata, Reviews of Modern Physics. 55 601-644, 1983.
4. Pries W., Thanaılakıs A., Card H.C. Group properties of cellular automata and Vlsı applications, IEEE Transactions on Computers. 35 1013-1024,1986.
5. Inokuchı S. On behaviors of cellular automata with rule 156, Bulletin of Informatics and Cybernetics. 30 121-131, 1998.
6. Wolfram S., Packard N.H. Two dimensional cellular auto-mata, Journal of Statistical Physics. 38 5-6, 1985.
7. Das A.K., Chaudhurı P.P. Vector space theoretic analysis of additive cellular automata and its applications for pseudo exhaustive test pattern generation, IEEE Transactions on Computers. 42 340-352, 1993.
8. Khan A.R., Choudhury P.P., Dihidar K., Mitra S., Sarkar P. VLSI architecture of a cellular automata, Computers Mathematics with Applications. 33 79-94, 997.

9. Chattopadhyay P., Choudhury P.P., Dihidar K. Characte-rization of a particular hybrid transformation of two-dimensional cellular automata, Computers Mathematics with Applications. 38 207-216, 1999.
10. Dihidar K., Choudhury P. P. Matrix algebraic formulae concerning some exceptional rules of two dimensional cellular automata, Information Sciences. 165 91-101, 2004.
11. Siap I., Akin H., Sah F. Characterization of two dimensi-onal cellular automata over ternary fields, Journal of the Franklin Institute. 348 1258-1275, 2011.
12. Tsalides P., Hicks P.J., York T.A. Three dimensional cel- lular automata and VLSI applications, IEE Proceedıngs. 136 490-495,1989.
13. Gerling R.W. Classification of three-dimensional cellular automata, Physcia A. 162 187-195, 1989.
14. Hemmingsson J.A. Totalistic three dimensional cellular automata withquasiperiodic behaviour, Physica A. Statistical Mechanics and its Applications. 183 255-261, 1992.
15. Brown S.G.R, Bruce N.B. Three-dimensional cellular automaton models of microstructural evolution during solidification, Journal of Materials Science. 30 1144-1150, 1995.
16. Leubeck E.G., De Gunst, M.C.M. A sterological method for the analysis of cellular lesions in tissue sections using three-dimensional cellular automata, Mathematical and Computer Modelling. 33 1387-1400, 2001.
17. Agapie A. Simple form of the stationary distribution for 3D cellular automata in a special case, Physica A. 389 2495-2499, 2010.
18. Morita K. Reversible computing and cellular automata-A survey, Theorical Computer Science. 395 101-131, 2008.
19. Cinkir Z., Akın H., Siap İ. Reversibility of 1D cellular automata with periodic boundary over finite fields Z_p, Journal of Statistical Physics. 143 807-823, 2011.
20. Akın H., Siap İ., Sah F. On 1D reversible cellular automata with reflective boundary over the prime field of order p, International Journal of Modern Physics C. 23 1-13, 2012.
21. Chang C.H., Su J.Y, Akın H., Sah F. Reversibility problem of multidimensional finite cellular automata, Journal of Statistical Physics. 168 208-231, 2017.