Design of Cellular Automata Models A Mathematical and A Replicative Perspectives

Abstract

Cellular Automaton (CA) is a parallel abstract machine, which consists of a sequence newlineof either finite or infinite number of simple, identical cells that interact locally and operate newlinein parallel on an nand#8722; dimensional lattice, where n = 1, 2, 3, · · · and each cell on the newlinelattice can be any one state of the finite state set. In this thesis, we discuss applications of newlineCA based model with two different perspectives: one a mathematical perspective where newlinewe model CA for computation of newlineand#65533; b newlinea f(x)dx, and another for a replicative perspective newlinewhere we investigate CA model for replication purpose. newlineThe Definite Integral, I = newlineand#65533; b newlinea f(x)dx, is defined as the signed area of the region newlinebounded by graph of the function. The existing mathematical methods (such as Darboux newlineintegral) are not computing the exact value of I in polynomial time. For that reason, newlinewe depend on the numerical methods (such as Simpson s) to compute the approximate newlinevalue of I instead of mathematical methods. But, the error bounds of these numerical newlinemethods depend on the existence of higher derivatives of the function. As such, there is newlineno mathematical as well as algorithmic model to compute I whose error bound doesn t newlinedepend on the higher order derivatives. In the present work, we propose a new cellular newlineautomaton based model for computing an approximate value of I and also observe that newlinethe level of accuracy is higher than the Simpsons rule and Monte Carlo integration. newlineReplication is defined as the process of generating exactly two perfect non-overlapping newlinecopies of any image. In the existing literature, all researchers have independently observed newline(without proof) that replication occurs at 2n th time step on 1and#8722;dimensional and newline2and#8722;dimensional CA models. In the present work, we compute the exact time for replication newlineof a binary image and also derive a relationship among the size of the image (m), newlinerule (rule neighborhood r) and number of time steps. newline newline