Characterization of 1-d Periodic Boundary Reversible CA

This paper reports characterization of one dimensional 3-neighborhood periodic boundary cellular automata (CA). It targets characterization of CA rules for efficient synthesis of reversible CA. The concept of reachability tree, as it has been proposed in [Sukanta Das, Anirban Kundu, Biplab K. Sikdar, and P. Pal Chaudhuri. Design of Nonlinear CA Based TPG Without Prohibited Pattern Set In Linear Time. Journal of Electronic Testing: Theory and Applications, 21:95–109, January 2005; Sukanta Das and Biplab K. Sikdar. Classification of CA Rules Targeting Synthesis of Reversible Cellular Automata. In Proceedings of International Conference on Cellular Automata for Research and Industry, ACRI, France, pages 68–77, September 2006; Sukanta Das, Biplab K. Sikdar, and P. Pal Chaudhuri. Characterization of Reachable/Nonreachable Cellular Automata States. In Proceedings of Sixth International Conference on Cellular Automata for Research and Industry, ACRI, The Netherlands, pages 813–822, October 2004], is redefined to classify the CA rules that can form a reversible CA. Such classification also enables synthesis of a reversible periodic boundary CA in linear time.