Volume 33, Issue 1 (2024)

A Generic NSRTD Framework for Characterizing Cellular Automaton Rules in Constant (0/1) Boundary Conditions

Som Banerjee
Mamata Dalui
Department of Computer Science and Engineering
National Institute of Technology, Durgapur
West Bengal 713209, India
Suvadip Hazra
Department of Computer Science and Engineering
ITER, Siksha ‘O’ Anusandhan
Bhubaneshwar 751030, India

Abstract

The cellular automaton (CA) is a rapidly emerging computational model that is widely used in different areas of simulations and scientific applications, as it can solve complex problems using simple rules. Cellular automata (CAs) are largely used in VLSI systems, fault detection, cryptography and other fields. In most of these applications, 2-state 3-neighborhood one-dimensional CAs are used. Some of the work on characterizing elementary CA (ECA) rules has been done, but all such work mainly focuses on a specific boundary condition (i.e., null, periodic boundary). This paper targets the design and development of a generic framework for the next state rule minterm transition diagram (NSRTD), referred to as the generic NSRTD (G-NSRTD), for constant (0/1) boundary conditions. By utilizing the developed G-NSRTD framework, which is reconfigurable based on the chosen boundary condition (constant-0/1), ECA rules can be characterized for both null and constant-1 boundary conditions. Hence, the current paper also focuses on characterizing all 256 ECA rules in constant (0/1) boundary conditions using the developed G-NSRTD framework, leading to the identification of all CA rules forming uniform single length cycle single-attractor CAs (SACAs), single length cycle two-attractor CAs (TACAs) and single length cycle multi-attractor CAs (MACAs) for arbitrary CA length n. Some of the relevant CA theories related to the characterization of ECA rules in constant (0/1) boundary conditions have been developed and reported accordingly.

Keywords: cellular automata; SACA; TACA; MACA; fixed-point attractor; NSRTD; constant (0/1) boundary CA  

Cite this publication as:
S. Banerjee, M. Dalui and S. Hazra, “A Generic NSRTD Framework for Characterizing Cellular Automaton Rules in Constant (0/1) Boundary Conditions,” Complex Systems, 33(1), 2024 pp. 61–86.
https://doi.org/10.25088/ComplexSystems.33.1.61