main| new issue| archive| editorial board| for the authors| publishing house|
Ðóññêèé
Main page
New issue
Archive of articles
Editorial board
For the authors
Publishing house

 

 


ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 11. Vol. 30. 2024

DOI: 10.17587/it.30.571-578

N. A. Matolygina, Laboratory Assistant, M. L. Gromov, PhD, Associate Professor,
Tomsk State University, Tomsk, Russian Federation

Matrix Model of Deterministic Synchronous Cellular Automata

The paper presents an approach for modeling deterministic synchronous cellular automata by matrices and operations on them. It is proposed to renumber the states of the automaton and write down a matrix, the elements of which are the current states (numbers associated with them) of the cells of the automaton. It is proposed to calculate the matrix of cell states in the next cycle in two stages: find the convolution of the current matrix with a special core, and map the resulting convolution matrix into the matrix of cell states in the next cycle. The convolution core is determined by the cell neighborhood pattern, and the convolution mapping to the matrix of the following states is based on the transition function of the automaton.
Keywords: cellular automaton, matrix, matrix convolution, mathematical modeling

P. 571-578

 

References

 

  1. Von Neumann J. Theory of Self-reproducing Automata, Urbana and London, University of Illinois Press, 1966, 403 p.
  2. Toffolli T. Cellular Automata Machines, Cambridge, Massachusetts and London, The MIT Press, 1987, 279 p.
  3. Hardy J., Pomeau Y., de Pazzis O. 2D Lattice-Gas model, J. Math. Phys. , 1973, no. 14, pp. 1746.
  4. Medvedev Yu. G. Application of a cellular automaton model of viscous fluid flow in the study of three-dimensional porous media, Avtometriya, 2006, vol. 42, no. 3, pp. 21—31 (in Russian).
  5. Malinetskii G. G., Stepantsov M. E. Simulation of dif­fusion processes using cellular automata with Margolus neighborhood, Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki, 1999, vol. 38, no. 6, pp. 1017—1020 (in Russian).
  6. Ochoa Bique A. O., Goryunov A. G., Manenti F. A com­parison of simulation techniques for uranium crystallization process, Chemical engineering transactions, 2015, vol. 43, pp. 793—798.
  7. Batani D., Biava S., Bittanti S., Previdi F. A cellular automaton model of laser—plasma interactions, Laser and Particle Beams, 2001, vol. 19, iss. 04, pp. 631—642.
  8. Zhang L., Shiri S., Garoni T. M. A Study of Aggregated Speed in Road Networks Using Cellular Automata, Lecture Notes in Computer Science, 2014, vol. 8751, pp. 596—605.
  9. Sabelfeld K. K., Kireeva A. A. Parallel implementation of a stochastic cellular automaton model of electron and hole recombination in 2D and 3D inhomogeneous semiconductors, Vestnik YuUrGU. Seriya: Vychislitelnaya matematika i informatika, 2017, vol. 6, no 1, pp. 87—103.
  10. Gibson M., Keedwell Ed., Savic D. An investigation of the efficient implementation of Cellular Automata on multicore CPU and GPU hardware, Journal of Parallel and Distributed Computing, 2015, vol. 77, pp. 11—25.
  11. Szkoda S., Koza Z., Tykierko M. Accelerating cellular automata simulations using AVX and CUDA, ARXIV, 2012, URL: https://arxiv.org/abs/1208.2428 (access date: 02.08.2024).
  12. Shalyapina N. A., Gromov M. L. "LIFE" in tensors: modeling cellular automata using video cards, Trudy ISP RAN, 2019, vol. 31, iss. 3, pp. 217—228, doi: 10.15514/ISPRAS-2019-31(3)-17 (in Russian).
  13. Subbotina A. Yu., Khokhlov N. I. Implementation of cellular automata "the game of Life" and the Kohomoto—Oono cellular automaton using technology MPI, Komputirnye issledovania i modelirovanie, 2010, vol. 2, no. 3, pp. 319—322 (in Russian).
  14. Kalgin K. V. Parallel implementation of asynchronous cel­lular automata on a 32-core computer system, Sibirskii zhurnal vychislitelnoi matematiki, 2012, vol. 15, no. 1, pp. 55—65 (in Russian).
  15. Szkoda S., Koza Z., Tykierko M. Multi-GPGPU Cellular Automata Simulations using OpenACC, Zenodo, 2014, pp. 1—6.
  16. Malyshkin V. Active Knowledge, LuNA and Literacy for Oncoming Centuries, Lecture Notes in Computer Science, 2015, vol. 9465, pp. 292—303.
  17. Perepelkin V. A. LuNA system for automatic construction of numerical parallel programs for multicomputers, Problems of Informatics, 2022, no 1, pp. 1—9.
  18. Markova V. P., Ostapkevich M. B. The comparison of MPI and LuNA capabilities using the implementation of cellular automata wave interference, Problems of Informatics, 2017, no. 2, pp. 53—64.
  19. Matolygina N. A., Gromov M. L., Matolygin A. K. Application of the tensor approach to the software implementation of the cellular automaton flow model, Problemy informatiki, 2023, no. 2, pp. 74—85 (in Russian).
  20. Gromov M., Shalyapina N., Matolygin A. Representation of Particle Shift in the FHP Model by TensorFlow Operations, Proceedings of International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), 2019, pp. 90—92.
  21. Matolygin A. K., Shalyapina N. A., Gromov M. L., Torgaev S. N. Tensor approach to software implementation of cellular automata model of diffusion, J. Phys.: Conf. Ser., 2020, vol. 1680, pp. 1—6.
  22. TensorFlow, URL: https://www.tensorflow.org (access date: 01.08.2024).
  23. Moore E. F. Gedanken-experiments on sequential machines, Automata Studies, ed. C. Shannon and J. McCarthy, Princeton, Princeton University Press, 1956, vol. 34, pp. 129—153.
  24. Gardner M. The fantastic combinations of John Conway's new solitaire game "Life", Scientific American, 1970, vol. 223, no. 4, pp. 120—123.
  25. Domasevich M. A., Rubtsov S. E., Pavlova A. V. Implementation of KA models of physical processes on triangulation grids, Ekologicheskii vestnik nauchnykh tsentrov ChES, 2020, vol. 17, no. 3, pp. 13—21 (in Russian).
  26. Frisch U., Hasslacher B., Pomeau Y. Lattice-Gas automata for Navier-Stokes equations, Phys. Rev. Lett., 1986, vol. 56, no. 14, pp. 1505—1508.

 

To the contents