International Journal of Mathematics and Mathematical Sciences
Volume 2011 (2011), Article ID 605098, 16 pages
doi:10.1155/2011/605098
Research Article

Characterization of the Evolution of Nonlinear Uniform Cellular Automata in the Light of Deviant States

1Applied Statistics Unit, Indian Statistical Institute, Kolkata 700108, India
2Department of Computer Science, Institute of Mathematics and Applications, Andharua, Bhubaneswar 751003, India
3Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 12180-3590, USA

Received 4 December 2010; Accepted 21 February 2011

Academic Editor: Marco Squassina

Copyright © 2011 Pabitra Pal Choudhury et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Dynamics of a nonlinear cellular automaton (CA) is, in general asymmetric, irregular, and unpredictable as opposed to that of a linear CA, which is highly systematic and tractable, primarily due to the presence of a matrix handle. In this paper, we present a novel technique of studying the properties of the State Transition Diagram of a nonlinear uniform one-dimensional cellular automaton in terms of its deviation from a suggested linear model. We have considered mainly elementary cellular automata with neighborhood of size three, and, in order to facilitate our analysis, we have classified the Boolean functions of three variables on the basis of number and position(s) of bit mismatch with linear rules. The concept of deviant and nondeviant states is introduced, and hence an algorithm is proposed for deducing the State Transition Diagram of a nonlinear CA rule from that of its nearest linear rule. A parameter called the proportion of deviant states is introduced, and its dependence on the length of the CA is studied for a particular class of nonlinear rules.