Solutions on 1-D and 2-D Density Classification Problem Using Programmable Cellular Automata
Sudhakar Sahoo, Pabitra Pal Choudhury, Amita Pal and Birendra Kumar Nayak
s paper deals with the solutions to the problem of Density Classification Task (DCT) using a variant of non-uniform Cellular Automata rules defined and named Programmable Cellular Automata (PCA). The translation properties as well as the density preserving properties of fundamental CA rules are explored. These two properties are utilized to develop different programmable CA to obtain the solution of Density Classification Task (DCT) both for 1-D and 2-D under periodic and fixed boundary conditions. The PCA based DCT solution rely on non-uniform CAs, with fixed rules for fixed boundaries, and rules changing along time for periodic boundary and can be generalisable to the other kinds of boundaries. Various solutions are explicitly given for the 1-D case; for 2-D, a single solution is discussed, and others could be derived, following the same principles of the solution given. Finally, the conventional problem of 2-D DCT is modified to arbitrary shapes and sizes, its applicability, and its solutions are discussed.
Keywords: Cellular Automata Rules, non-uniform Cellular Automata, Density Classification Task