An Analytical Framework for Characterizing Restricted Two Dimensional Cellular Automata Evolution
Shiladitya Munshi, Nirmalya Sundar Maiti, Deepan Ray, Debabrata Roy Chowdhury and P. Pal Chaudhuri
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.2m)time complexity.