Search

This paper studies chaotic behavior of 1-dimensional non-uniform cellular automata (CAs). The chaotic system is unpredictable in the long run. To understand the source of unpredictability, we add an information to a cell and check how it flows to its neighbors. That is, once the state of a cell is changed, the probability to which the change affects its neighbors, is calculated. The probabilistic value decides whether one cell communicates with another cell. Depending on the communication among cells, a binary relation over the set of cells is defined in this paper which is known as communication relation. It is shown that the relation should be an equivalence relation to make a cellular automaton (CA) chaotic. The equivalence relation among the cells form an equivalence class which is named as communication class. Another important property of a chaotic CA is transitivity of the CA. Transitivity of a CA does not allow disjoint subsets of a configuration space. Based on the communication class and transitivity property of a CA, we newly define the chaos in CA. Sometimes one cell may not be able to communicate with another cell due to blocking word. The presence of blocking word in a CA makes the CA non-transitive. This paper shows a method to find out such blocking words. Finally, a parametrization technique is developed in this work based on the transitivity, communication class and blocking words. Depending on the parameter value of a non-uniform CA, one can predict whether the behavior of the CA is chaotic.

This paper presents a study of chaos in one-dimensional cellular automata (CAs). The communication of information from one part of the system to another has been taken into consideration in this study. This communication is formalized as a binary relation over the set of cells. It is shown that this relation is an equivalence relation and all the cells form a single equivalence class when the cellular automaton (CA) is chaotic. However, the communication between two cells is sometimes blocked in some CAs by a subconfiguration which appears in between the cells during evolution. This blocking of communication by a subconfiguration has been analyzed in this paper with the help of de Bruijn graph. We identify two types of blocking — full and partial. Finally a parameter has been developed for the CAs. We show that the proposed parameter performs better than the existing parameters.