Volume 34, Issue 1 (2025)

Nonlinearity in Large-Cycle Cellular Automata

Sukanya Mukherjee
Department of Computer Science and Engineering
Institute of Engineering and Management Kolkata
University of Engineering and Management, Kolkata
700091, West Bengal, India
sukanyaiem@gmail.com
Sumit Adak
Department of Applied Mathematics and Computer Science
DTU Compute, Technical University of Denmark
Kgs. Lyngby, Denmark, 2800
suad@dtu.dk

Abstract

The class of maximal-length cellular automata (CAs) has gained significant attention over the last few years due to the fact that it can generate cycles with the longest possible lengths. For every l of the form $l=2^n-1$ where n∈N, a cycle of length l can be generated by a cellular automaton (CA) of size $\lfloor {\log }_{2}l\rfloor +1$; this maximal-length CA is in fact the optimal (minimum-sized) CA to generate a cycle of length l. However, maximal-length CAs are, in general, linear and have some drawbacks. Moreover, it is nontrivial to address this problem for any l∈N, that is, removing the constraint that l is of the form $2^n-1$. In this paper we therefore employ nonlinearity in the rules and aim to generate the near-optimal CA for any given cycle length l, meaning that the generated CAs will be of size $n=\left(\lfloor {\log }_{2}l\rfloor +1\right)+d$, where the displacement d is as small as possible. We use a generic operator to concatenate a collection of component CAs of sizes $n_1,n_2,\dots ,n_k$ by employing an evolutionary strategy. Here, $n=n_1+n_2+\cdots +n_k$ and $l\ge \mathrm{lcm}\left({\ell }_1,{\ell }_2,\dots ,{\ell }_k\right)$, where ${\ell }_i$ (1≤i≤k) is the maximum cycle length of a CA of size $n_i$. An influencing factor in the design of component CAs is to achieve the near-optimal CA for a given cycle length. Here we consider nonlinear reversible large-cycle CAs as component CAs. We also measure the effectiveness of nonlinearity in large-cycle generation.

Keywords: cellular automata; CAs; reversible CAs; large-cycle CA; nonlinearity; neighborhood dependent; evolution

Cite this publication as:
S. Mukherjee and S. Adak, “Nonlinearity in Large-Cycle Cellular Automata,” Complex Systems, 34(1), 2025 pp. 129–160.
https://doi.org/10.25088/ComplexSystems.34.1.129