Definition and application of a five-parameter characterization of one-dimensional cellular automata rule space

Using compression to find interesting one-dimensional cellular automata

This paper proposes a novel method for finding interesting behaviour in complex systems based on compression. A new clustering algorithm has been designed and applied specifically for clustering 1D elementary cellular automata behaviour using the prediction by partial matching (PPM) compression scheme, with the results gathered to find interesting behaviours. This new algorithm is then compared with other clustering algorithms in Weka and the new algorithm is found to be more effective at grouping behaviour that is visually similar in output. Using PPM compression, the rate of change of the cross-entropy with respect to time is calculated. These values are used in combination with a clustering algorithm, such as k-means, to create a new set of clusters for cellular automata. An analysis of the data in each cluster is then used to determine if a cluster can be classed as interesting. The clustering algorithm itself was able to find unusual behaviours, such as rules 167 and 181 which have output that is slightly different from all the other Sierpiński Triangle-like patterns, because their apexes are off-centre by one cell. When comparing the new algorithm with other established ones, it was discovered that the new algorithm was more effective in its ability to group interesting and unusual cellular automata behaviours together.

Evaluation of dynamic behavior forecasting parameters in the process of transition rule induction of unidimensional cellular automata

The simulation of the dynamics of a cellular systems based on cellular automata (CA) can be computationally expensive. This is particularly true when such simulation is part of a procedure of rule induction to find suitable transition rules for the CA. Several efforts have been described in the literature to make this problem more treatable. This work presents a study about the efficiency of dynamic behavior forecasting parameters (DBFPs) used for the induction of transition rules of CA for a specific problem: the classification by the majority rule. A total of 8 DBFPs were analyzed for the 31 best-performing rules found in the literature. Some of these DBFPs were highly correlated each other, meaning they yield the same information. Also, most rules presented values of the DBFPs very close each other. An evolutionary algorithm, based on gene expression programming, was developed for finding transition rules according a given preestablished behavior. The simulation of the dynamic behavior of the CA is not used to evaluate candidate transition rules. Instead, the average values for the DBFPs were used as reference. Experiments were done using the DBFPs separately and together. In both cases, the best induced transition rules were not acceptable solutions for the desired behavior of the CA. We conclude that, although the DBFPs represent interesting aspects of the dynamic behavior of CAs, the transition rule induction process still requires the simulation of the dynamics and cannot rely only on the DBFPs.

Quiescent string dominance parameter F and classification of one-dimensional cellular automata

The classification of rules may be one of the most fundamental targets in the study of cellular automata. In this paper, we propose a method for achieving such a classification, in which a new quiescent string dominance parameter F, which is orthogonal to lambda, is introduced. For N -neighbor and K -state cellular automata, in the region 1/K<lambda<1-1/K, the maximum F corresponds to the class III rules, and its minimum, to the class II or class I rules. Therefore, transition of the pattern class takes place between them without fail. By using lambda and F, the phase diagram of cellular automata is determined in the (lambda, F ) plane for five-neighbor and four-state cellular automata. The phase diagram indicates that along the F axis, class III rules are distributed in a large F region, while class I and class II rules are, in a small F region, and class IV rules are found in the overlapping region of class II and III rules. These distributions are almost independent of lambda. Along the lambda axis, all four pattern classes are found in the region 0.25<lambda<0.75, and no correlation between pattern class and lambda parameter is observed.