In this paper, the problem of identifying the cellular automata (CAs) is considered. We frame and solve this problem in the context of incomplete observations, i.e., prerecorded, incomplete configurations of the system at certain, and unknown time stamps. We consider 1-D, deterministic, two-state CAs only. An identification method based on a genetic algorithm with individuals of variable length is proposed. The experimental results show that the proposed method is highly effective. In addition, connections between the dynamical properties of CAs (Lyapunov exponents and behavioral classes) and the performance of the identification algorithm are established and analyzed.

The spatio-temporal dynamics of cellular automata (CAs) has attracted the attention of researchers from different fields, mainly mathematics, computer science and engineering, as a consequence of both the intriguing spatio-temporal patterns that these dynamical systems evolve and the fact that they enable the modelling of complex natural phenomena. Yet, to this day, there are only a few studies that focus on the automated classification of cellular automata on the basis of the space-time diagrams they evolve. Here, we present an innovative approach to classify CAs according to Wolfram's classification scheme in an automated way by relying on texture descriptors that capture the nature of the evolved space-time diagrams. More specifically, we propose the use of one of two well-known texture descriptors, namely Local Binary Pattern Variance and Fourier descriptors, to generate features grasping the diagrams' nature, followed by nearest neighbor classification. The performance of this approach is assessed through a cross-validation and by analysing the percentage of pre-classified rules that is required to arrive at an acceptable success rate. The experiments involve the family of elementary CAs and four families of totalistic CAs with neighborhood radii ranging from one to three, and a state space consisting of up to three states. The results show the potential of our proposal with success rates varying between 65% and 98% depending on the size of the training set, which ranges from 10% to 90% of the rules in the CA family at stake. For totalistic CAs, this training set should be classified manually to start the process of automated classification.

In this paper we consider the identification problem of Cellular Automata (CAs). The problem is defined and solved in the context of partial observations with time gaps of unknown length, i.e. pre-recorded, partial configurations of the system at certain, unknown time steps. A solution method based on a modified variant of a Genetic Algorithm (GA) is proposed and illustrated with brief experimental results.