On Invertible Three Neighborhood Null-Boundary Uniform Cellular Automata
Soumyabrata Ghosh
Nirmalya S. Maiti
P. Pal Chaudhuri
Cellular Automata Research Lab (CARL)
Alumnus Software Limited, Sector-V
Kolkata, West Bengal, India 700091
soumyabrata@alumnux.com
Biplab K. Sikdar
Department of Computer Science and Technology
Bengal Engineering and Science University, Shibpur
West Bengal, India 711103
Abstract
This paper solves the problem of determining the number of cells in an invertible three neighborhood null-boundary uniform cellular automaton (CA) by using its rule vector graph (RVG). The RVG represents an efficient data structure designed to characterize CA evolution and is derived out of its rule vector (RV). The concept of a horizontal rule vector subgraph (HRVS) is introduced to formulate the analytical framework of the solution. The RVG of a CA is partitioned into a number of identical HRVSs. It has been shown that invertible CA size depends on the size of the HRVS.
