Computation properties of spatial dynamics simulation by probabilistic cellular automata

摘要

Accuracy, stability and computation complexity of fine-grained parallel simulation of spatial dynamics by probabilistic cellular automata (CA), are assessed and experimentally studied. Under investigation are probabilistic CA constructed as a composition of an ordinary CA with a function given in real numbers. The accuracy problem is reduced to approximation error assessment of the transformation of a real spatial function into a Boolean array and addition of cellular arrays with different cell state alphabets: real and Boolean. Some techniques for determining simulation parameters which provide a given accuracy are given. Stability is shown to be dependent only on real function, the CA component of the dynamics having no effect on it. Computation complexity of simulation process is also assessed. Some experimental results supporting the theoretical conclusions are presented.