Characterization of Nonlinear Cellular Automata Having Only Single Length Cycle Attractors
Nazma Naskar, Sukanta Das and Biplab K. Sikdar
Characterization of a special class of cellular automata (CA) having only point attractors is the necessity to devise CA based solutions for diverse applications, like pattern classification, pattern recognition, etc. This work explores the essential properties of attractors towards characterization of the 1-dimensional nonlinear CA with point attractors (single length cycle attractors). The concept of Reachability Tree is introduced for such characterization. It enables identification of the pseudoexhaustive bits (PE-bits) of a CA defining the point attractors. The theoretical framework, developed, is found to be most effective to devise schemes for synthesizing a single length cycle multiple attractor CA, in linear time, for a given set of attractors with the specific set of PE-bits. This finally enables classification of CA rules that can be employed for synthesizing an n-cell CA, for an arbitrary n, having single length cycle attractors only.
Keywords: Cellular automata, attractor, pseudo-exhaustive (PE) bit, point attractor, reachability tree