A Novel Subset Graph Algorithm for Generating Reversible One-Dimensional Cellular Automata

Abstract

In this study, a novel algorithm for generating reversible rules with null boundary conditions for one-dimensional Cellular Automata (CA) is presented. The neighborhood vector of the CA is used by the procedure to create a subset graph. It finds reversible transition rules by examining the connectivity attributes of the graph itself. By ensuring a distinct predecessor and successor for every configuration, this assures bijectivity. In fields like complex system simulations and cryptography, reversibility is essential. This method overcomes the drawbacks of previous approaches, such as the complexity of de Bruijn graphs and the scalability issues with transition matrices. The suggested method's scalability and usefulness are demonstrated by theoretical analysis and illustrative examples. The results suggest the algorithm's efficiency in generating reversible CA rules, making it suitable for various applications requiring precise and reliable computational reversibility.