Volume 35, Issue 2 (2026)

Second-Order Three-Neighbor Number-Conserving
Cellular Automata

Akiko Fukuda
Department of Mathematical Sciences, Shibaura Institute of Technology
307 Fukasaku, Minuma-ku, Saitama-shi, Saitama 337-8570, Japan
Sennosuke Watanabe
Faculty of Informatics, The University of Fukuchiyama
3370 Azahori, Fukuchiyama, Kyoto 620-0886, Japan
Yuki Nishida
Department of Science, Technology and Informatics
Kyoto Prefectural University
1-5 Shimogamo Hangi-cho, Sakyo-ku, Kyoto 606-8522, Japan
Junta Matsukidaira
Faculty of Advanced Science and Technology, Ryukoku University
1-5 Yokotani, Seta Oe-cho, Otsu, Shiga 520-2194, Japan

Abstract

In this paper, the number-conserving rules for second-order three-neighbor binary cellular automata (SOCAs) are discussed. The SOCAs include the well-known elementary cellular automata and elementary reversible cellular automata and have a total of $2^{64}$ local rules. We show that the number of number-conserving SOCAs is limited to 74 through a polynomial representation of the local rules. A concrete description of the polynomial representation for 15 representative rules is provided. In addition, we establish a necessary and sufficient condition for each SOCA to be number conserving. This condition can be regarded as a discrete version of the flux form in fluid dynamics.

Keywords: second-order cellular automata; number conservation; polynomial representation; flux form

Cite this publication as:
A. Fukuda, S. Watanabe, Y. Nishida and J. Matsukidaira, “Second-Order Three-Neighbor Number-Conserving Cellular Automata,” Complex Systems, 35(2), 2026 pp. 119–140.
https://doi.org/10.25088/ComplexSystems.35.2.119