An Analytical Framework for Characterizing Restricted Two Dimensional Cellular Automata Evolution
This paper reports an analytical framework to study a restricted class of Two Dimensional CA. The imposed restriction enables characterization of 2DCA evolution. The concept of Rule Vector Graph (RVG) introduced in [6,7] for characterizing one dimensional CA has been extended in this paper for 2DCA. Design of Rule Vector Graph (RVG) for restricted class of 2DCA is reported. Analysis of RVG enables identification of necessary and sufficient conditions for a 2DCA to be invertible. Further, traversal of the RVG enables checking of reversibility and also identification of all Non-Reachable States (NRSs) and Self Loop States (SLSs) of a (m * n) 2DCA in O(n.2(m)) time complexity.
rule vector graph (rvg) 2d cellular automata (2dca) restricted 2d ca serializable rule