Replication in Two-Dimensional Cellular Automaton with Linear Rules
U Srinivasa Rao, L Jeganathan and Tessy Mathew
A two-state, two-dimensional cellular automaton (2D CA) with uniform linear rules on 9−neighborhood renders multiple copies of any two-dimensional binary image as an initial configuration. In total, there are 512 linear rules and these rules are classified into groups of nine basis of their capacities in producing the number of copies of a given image and these groups are Group-1, Group-2, · · · , Group-9. All groups other than Group-1 have been found to be generating multiple copies for a given image at time t = 2𝑛 where 𝑛 ≥ 0. A relation was derived among the size of a binary image, neighborhood and exact time for replication (two non-overlapping copies) in one-dimensional cellular automaton (1D CA). In this paper, we classify the Group-2 rules into four classes based on the directions of the translation of two copies of an image on the grid. The four classes as Horizontal rules, Vertical rules, Diagonal rules and Combination rules. We have computed the exact time for replication of a given binary image for each class separately.
Keywords: Cellular automaton, linear rules, multiple copies, replication, image processing