Synthesis of Scalable Single Length Cycle, Single Attractor Cellular Automata in Linear Time
Bidesh Chakraborty
Department of Computer Science and Engineering
Haldia Institute of Technology, Haldia
Purba Medinipur, West Bengal 721657, India
Mamata Dalui
Department of Computer Science and Engineering
National Institute of Technology, Durgapur
Paschim Burdwan, West Bengal 713209, India
Biplab K. Sikdar
Department of Computer Science and Technology
Indian Institute of Engineering Science and Technology, Shibpur
Howrah, West Bengal 711103, India
Abstract
This paper proposes the synthesis of single length cycle, single attractor cellular automata (SACAs) for arbitrary length. The n-cell single length cycle, single attractor cellular automaton (SACA), synthesized in linear time O(n), generates a pattern and finally settles to a point state called the single length cycle attractor state. An analytical framework is developed around the graph-based tool referred to as the next state transition diagram to explore the properties of SACA rules for three-neighborhood, one-dimensional cellular automata. This enables synthesis of an (n+1)-cell SACA from the available configuration of an n-cell SACA in constant time and an (n+m)-cell SACA from the available configuration of n-cell and m-cell SACAs also in constant time.
Keywords: cellular automata; single length cycle, single attractor cellular automata; SACA; scalable test structure; NSRTD; linear time
Cite this publication as:
B. Chakraborty, M. Dalui and B. K. Sikdar, “Synthesis of Scalable Single Length Cycle, Single Attractor Cellular Automata in Linear Time,” Complex Systems, 30(3), 2021 pp. 415–439.
https://doi.org/10.25088/ComplexSystems.30.3.415
