Volume 34, Issue 1 (2025)

Exploring Nonuniform Structure of NSRTDs for Characterizing MACA Rules in the Null-Boundary Condition

Suvadip Hazra
Department of Computer Science and Engineering
Indian Institute of Information Technology Dharwad
Karnataka 58009, India
Som Banerjee
Mamata Dalui
Department of Computer Science and Engineering
National Institute of Technology, Durgapur
West Bengal 713209, India
Bidesh Chakraborty
Department of Computer Science and Engineering
Haldia Institute of Technology, Haldia
West Bengal 721657, India

Abstract

The cellular automaton (CA), a discrete model, is gaining popularity in simulations and scientific exploration across various domains, including cryptography, error-correcting codes, VLSI design and test pattern generation. This paper examines a two-state three-neighborhood nonuniform finite CA with a specified number of fixed points. We utilize a graph-based tool known as the next state rule minterm transition diagram (NSRTD) to analyze the spatiotemporal behavior of these cellular automata (CAs) across all lengths. We devise methods for synthesizing nonuniform single length cycle multi-attractor CAs (MACAs), a specialized class of irreversible CA with a predefined number of fixed points for any arbitrary length. Despite the method’s exponential worst-case time complexity, it offers the advantage of selecting rules for each CA cell from a set of candidate rules, ensuring the desired number of fixed points.

Keywords: cellular automata; length cycle multi-attractor cellular automata; MACA; next state rule minterm transition diagram; NSRTD; fixed-point attractor

Cite this publication as:
S. Hazra, S. Banerjee, M. Dalui and B. Chakraborty, “Exploring Nonuniform Structure of NSRTDs for Characterizing MACA Rules in the Null-Boundary Condition,” Complex Systems, 34(1), 2025 pp. 91–127.
https://doi.org/10.25088/ComplexSystems.34.1.91