Rule Vector Graph (RVG) To Design Linear Time Algorithm for Identifying the Invertibility of Periodic-Boundary Three Neighborhood Cellular Automata
Nirmalya S. Maiti, Soumyabrata Ghosh, Biplab K. Sikdar and P. Pal Chaudhuri
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].
Keywords: Uniform CA, Hybrid CA, Periodic Boundary CA, Rule Vector Graph (RVG), Non-Reachable States (NRSs), Rule Min Term, Invertible CA, Elementary Group Rules.