Rule Vector Graph (RVG) To Design Linear Time Algorithm for Identifying the Invertibility of Periodic-Boundary Three Neighborhood Cellular Automata
This paper reports an algorithm to check the invertibility of Periodic-Boundary 3-Neighborhood Cellular Automata (CA) employing any rule - linear/additive and non-linear. The complexity of the proposed algorithm is linear. An efficient data structure called Rule Vector Graph (RVG) is reported in [41] to represent global functionality of a Null Boundary CA by its Rule Vector. However, construction of the RVG of a Periodic Boundary CA demands some modifications that are reported in this paper. The RVG of a Periodic-Boundary invertible CA preserves the specific characteristics that can be checked in linear time. It also solves the problem of determining the number of cells in an invertible three neighborhood periodic boundary uniform CA. Its counterpart for null boundary CA has been reported in [42].
rule vector graph (rvg) periodic boundary ca invertible ca uniform ca hybrid ca non-reachable states (nrss) rule min term elementary group rules