PaperNo Access

Construction of One-Dimensional Nonuniform Number Conserving Elementary Cellular Automata Rules

Suryakanta Pal

Model Degree College, Malkangiri, Odisha 764045, India

E-mail Address: surya_tuna@yahoo.co.in

Search for more papers by this author

Sudhakar Sahoo

https://orcid.org/0000-0003-3689-8230

Institute of Mathematics and Applications, Bhubaneswar 751029, India

E-mail Address: sudhakar.sahoo@gmail.com

Search for more papers by this author

, and

Birendra Kumar Nayak

P. G. Department of Mathematics, Utkal University, Bhubaneswar 751004, India

E-mail Address: bknatuu@yahoo.co.uk

Search for more papers by this author

https://doi.org/10.1142/S0218127421500723Cited by:3 (Source: Crossref)

Abstract

An effort to study one-dimensional nonuniform elementary number conserving cellular automata (NCCA) rules from an exponential order rule space of cellular automata is an excellent computational task. To perform this task effectively, a mathematical heritage under the number of conserving functions over binary strings of length $n$ has been highlighted along with their number conserving cellular automata rules (either uniform or nonuniform). A basic approach for the construction of some feasible nonuniform NCCA rules of any finite configuration with the assistance of nine uniform elementary CA rules has been investigated. From our construction procedure, recurrence equations are formulated as suitably solved to ascertain the actual range of NCCA rules. The state transition diagrams (STDs) of NCCA rules are analyzed. While classifying the binary strings through STDs, we found a fascinating optical insight that equal weight strings from a class whose cardinality is the same as the binomial coefficient $C (n, k)$ where $n$ is the length and $k$ is the weight of the binary string.

Keywords:

References

Boccara, N. & Fukś, H. [1998] “ Cellular automata rules conserving the number of active sites,” J. Phys. A: Math. Gen. 31, 6007–6018. Crossref, Google Scholar
Boccara, N. & Fukś, H. [2002] “ Number conserving cellular automaton rules,” Fundamenta Informaticae 52, 1–13. Web of Science, Google Scholar
Boccara, N. [2007] “ Eventually number conserving cellular automata,” Int. J. Mod. Phys. C 18, 35–42. Link, Web of Science, Google Scholar
Durand, B., Formenti, E. & Róka, Z. [2003a] “ Number conserving cellular automata I: Decidability,” Theoret. Comput. Sci. 299, 523–535. Crossref, Web of Science, Google Scholar
Durand, B., Formenti, E., Grange A. & Róka, Z. [2003b] “ Number conserving cellular automata: New results on decidability and dynamics,” DMTCS Proc., Vol. AB, pp. 129–140. Crossref, Google Scholar
Formenti, E. & Grange, A. [2003] “ Number conserving cellular automata II: Dynamics,” Theoret. Comput. Sci. 304, 269–290. Crossref, Web of Science, Google Scholar
Fukś, H. [2004] “ Critical behaviour of number-conserving cellular automata with nonlinear fundamental diagrams,” J. Statist. Mech.: Th. Experim. 2004, https://doi.org/10.1088/1742-5468/2004/07/P07005. Google Scholar
Fukś, H. & Sullivan, K. [2007] “ Enumeration of number-conserving cellular automata rules with two inputs,” J. Cellul. Autom. 2, 141–148. Web of Science, Google Scholar
Gacs, P., Kurdyumov, G. L. & Levin, L. A. [1978] “ One dimensional uniform arrays that wash out finite islands,” Problemy Peredachi Informatsii 14, 92–98. Google Scholar
Hattori, T. & Takesue, S. [1991] “ Additive conserved quantities in discrete-time lattice dynamical systems,” Physica D 49, 295–322. Crossref, Web of Science, Google Scholar
Hazari, R. & Das, S. [2014] “ Number conservation property of elementary cellular automata under asynchronous update,” Compl. Syst. 23, 177–195. Crossref, Google Scholar
Hazari, R. & Das, S. [2016] “On number conservation of non-uniform cellular automata,” arXiv:1604.06600v1. Google Scholar
Hazari, R. & Das, S. [2018] “ Number conservation property of binary cellular automata under $α$ -asynchronous update,” J. Cellul. Autom. 13, 247–265. Web of Science, Google Scholar
Imai, K., Fujita, K., Iswamoto, C. & Morita, K. [2002] “ Embedding a logically universal model and a self-reproducing model into number-conserving cellular automata,” Int. Conf. Unconventional Methods of Computation, pp. 164–175. Crossref, Google Scholar
Kohyama, T. [1989] “ Cellular automata with particle conservation,” Progr. Theoret. Phys. 81, 47–59. Crossref, Google Scholar
Kohyama, T. [1991] “ Cluster growth in particle-conserving cellular automata,” J. Statist. Phys. 63, 637–651. Crossref, Web of Science, Google Scholar
Moreira, A. [2003] “ Universality and decidability of number-conserving cellular automata,” Theoret. Comput. Sci. 292, 711–721. Crossref, Web of Science, Google Scholar
Moreira, A., Boccara, N. & Goles, E. [2004] “ On conservative and monotone one-dimensional cellular automata and their particle representation,” Theoret. Comput. Sci. 325, 285–316. Crossref, Web of Science, Google Scholar
Morita, K. & Imai, K. [2001] “ Number-conserving reversible cellular automata and their computation-universality,” Theoret. Inform. Appl. 35, 239–258. Crossref, Web of Science, Google Scholar
Pal, S., Sahoo, S. & Nayak, B. K. [2019] “ Deterministic computing techniques for perfect density classification,” Int. J. Bifurcation and Chaos 29, 1950064-1–11. Link, Web of Science, Google Scholar
Pivato, M. [2002] “ Conservation laws in cellular automata,” Nonlinearity 15, 1781–1793. Crossref, Web of Science, Google Scholar
Sahoo, S. & Choudhury, P. P. [2009] “Issues on drawing the state transition diagram for arbitary cellular automata,” arXiv:0811.1513(nlin.CG). Google Scholar
Sahoo, S., Choudhury, P. P., Pal, A. & Nayak, B. K. [2013] “ Solutions on 1D and 2D density classification problem using programmable cellular automata,” J. Cellul. Autom. 9, 59–88. Web of Science, Google Scholar
Takesue, S. [1995] “ Staggered invariants in cellular automata,” Compl. Syst. 9, 149–168. Google Scholar
Tanimoto, N. & Imai, K. [2009] “ A characterization of von Neumann neighbor number-conserving cellular automata,” J. Cellul. Autom. 4, 39–54. Web of Science, Google Scholar
Wolfram, S. [2002] A New Kind of Science (Wolfram Media, Inc., Champaign, IL). Google Scholar
Wolnik, B. & De Baets, B. [2019] “ All binary number-conserving cellular automata based on adjacent cells are intrinsically one-dimensional,” Phys. Rev. E 100, https://doi.org/10.1103/PhysRevE.100.022126. Crossref, Web of Science, Google Scholar