On linear cellular automata

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

Wolfram cellular automata are considered and their operation is demonstrated using an example of traffic flow simulation. For the class of one-dimensional elementary cellular automata, the concept of linearity is introduced in the language of Zhegalkin operators. An algorithm for finding linear Zhegalkin operators with multipliers of three variables is presented. The algorithm is implemented in Python.

Full Text

Restricted Access

About the authors

V. R. Kulikov

Siberian State University

Author for correspondence.
Email: v.r.kulikov@mail.ru
Russian Federation, Krasnoyarsk

А. А. Kytmanov

MIREA – Russian Technological University

Email: aakytm@gmail.com
Russian Federation, Moscow

А. О. Poroshin

Siberian State University

Email: poroshin.012332@gmail.com
Russian Federation, Krasnoyarsk

I. V. Timofeev

Kirensky Institute of Physics, Federal Research Center KSC SB RAS; Siberian State University

Email: tiv@iph.krasn.ru
Russian Federation, Krasnoyarsk; Krasnoyarsk

D. P. Fedchenko

Kirensky Institute of Physics, Federal Research Center KSC SB RAS; Siberian State University

Email: fdp@iph.krasn.ru
Russian Federation, Krasnoyarsk; Krasnoyarsk

References

  1. von Neumann J. Theory of Self-Reproducing Automata, Ed. by Burks, A.W., Urbana: Illinois Univ. Press, 1966.
  2. Tsetlin M.L. Some problems of finite state machine behavior, Dokl. Akad. Nauk SSSR, 1961, vol. 139, no. 4, pp. 830–833.
  3. Conway J. et al. The game of life, Sci. Amer., vol. 223, no. 4, p. 4.
  4. Batty M. Cities as Complex systems: Scaling, interaction, networks, dynamics and urban morphologies, in Encyclopedia of Complexity and Systems Science, 2009, pp. 1041–1071.
  5. Ghosh P. et al. Application of cellular automata and Markov-chain model in geospatial environmental modeling—A review, Remote Sens. Appl.: Soc. Env., 2017, vol. 5, pp. 64–77.
  6. Introduction to Mathemetical Modeling of Traffic Flows, Ed. by Gasnikov, A. et al. Litres, 2022 [in Russian].
  7. Fronczak P. et al. Cellular automata approach to modeling self-organized periodic patterns in nanoparticle-doped liquid crystals, Phys. Rev. E., 2022, vol. 106, no. 4, p. 44705.
  8. Janssens K.G.F. An introductory review of cellular automata modeling of moving grain boundaries in polycrystalline materials, Math. Comput. in Simul., 2010, vol. 80, no. 7, pp. 1361–1381.
  9. Lemont B.K. and Seybold P.G. Cellular automata modeling of complex biochemical systems, in Encyclopedia of Complexity and Systems Science, 2015.
  10. Kozhoridze G., Dor E.B., and Sternberg M. Assessing the dynamics of plant species invasion in Eastern-Mediterranean Coastal Dunes Using Cellular Automata Modeling and Satellite Time-Series Analyses, Remote Sens., 2022, vol. 14, no. 4, p. 1014.
  11. Wolfram S. Statistical mechanics of cellular automata, Rev. Modern Phys., 1983, vol. 55, no. 3., p. 601.
  12. Wolfram S. et al. A New Kind of Science, Champaign: Wolfram Media, 2002, vol. 5, p. 130.
  13. Tomassini M., Sipper M., and Perrenoud M. On the generation of high-quality random numbers by two-dimensional cellular automata, IEEE Trans. Comput., 2000, vol. 49, no. 10, pp. 1146–1151.
  14. Walus K. et al. RAM design using quantum-dot cellular automata, NanoTechnology Conference, 2003, Vol. 2, pp. 160–163.
  15. Cagigas-Muniz D. et al. Efficient simulation execution of cellular automata on GPU, Simul. Modell. Pract. Theory, 2022, vol. 118, p. 102519.
  16. Sato T. Decidability for some problems of linear cellular automata over finite commutative rings, Inf. Proc. Lett., 993, vol 46, no. 3, pp. 151–155.
  17. Martin A. et al. Reversibility of linear cellular automata, Appl. Math. Comput., 2011, vol. 217, no. 21, pp. 8360–8366.
  18. Martin del Rey A., Casado Vara R., and Hernández S. D. Reversibility of symmetric linear cellular automata with radius r = 3, Mathematics, 2019, vol. 7, no. 9, p. 816.
  19. Zhegalkin I.I. Arithmetization of symbolic logic, Mat. Sb., vol. 35, no. 3–4, pp. 311–377.
  20. Fedchenko D.P., Novikov V.V., and Timofeev I.V. Photonic topological insulators of the Rudner type in terms of of tricolor cellular automata, Uch. Zap. Fiz. Fakul’teta MGU, 2021, No. 5, p. 2150302.
  21. Fedchenko D.P., Kim P.N., and Timofeev I.V. Photonic topological insulator based on frustrated total internal reflection in array of coupled prism resonators, Symmetry, 2022, vol. 14, no. 12, p. 2673.
  22. Gal’perin G.A. and Zemlyakov A.N. Mathematical Billiards: Billiard Problems and Related Problems of Mathematics and Mechanics, Moscow: Nauka, 1990 [in Russian].

Supplementary files

Supplementary Files
Action
1. JATS XML
Download
2. Fig. 1. The rule of the cellular automaton with the Wolfram code W=254.

Download (29KB)
Indexing metadata
3. Fig. 2. The first 50 cycles of a cellular automaton with the Wolfram code W= 30 with a single-point initial state.

Download (244KB)
Indexing metadata
4. Fig. 3. All the rules of the cellular automaton, for which the state of the cell depends only on the states of neighboring cells.

Download (551KB)
Indexing metadata
5. Fig. 4. An element of a transport network modeled using a cellular automaton.

Download (198KB)
Indexing metadata
6. Fig. 5. The result of modeling the congestion of the transport network.

Download (184KB)
Indexing metadata
7. Fig. 6. Actions of Zhegalkin operators with multipliers of two variables.

Download (613KB)
Indexing metadata
8. Fig. 7. Zhegalkin linear operators with multipliers of three variables.

Download (266KB)
Indexing metadata
9. Fig. 8. Algorithm 1

Download (154KB)
Indexing metadata
10. Fig. 9. Algorithm 2

Download (267KB)
Indexing metadata
11. Fig. 10. Algorithm 3

Download (219KB)
Indexing metadata
12. Fig. 11. Algorithm 4

Download (368KB)
Indexing metadata

Copyright (c) 2024 Russian Academy of Sciences

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».