Automatic Texture Based Classification of the Dynamics of One-Dimensional Binary Cellular Automata

Automatic Texture Based Classification of the Dynamics of One-Dimensional Binary Cellular Automata

Marcelo Arbori Nogueira (Universidade Presbiteriana Mackenzie, São Paulo, Brazil) and Pedro Paulo Balbi de Oliveira (Universidade Presbiteriana Mackenzie, São Paulo, Brazil)
Copyright: © 2019 |Pages: 21
DOI: 10.4018/IJNCR.2019100104

Abstract

Cellular automata present great variability in their temporal evolutions due to the number of rules and initial configurations. The possibility of automatically classifying its dynamic behavior would be of great value when studying properties of its dynamics. By counting on elementary cellular automata, and considering its temporal evolution as binary images, the authors created a texture descriptor of the images - based on the neighborhood configurations of the cells in temporal evolutions - so that it could be associated to each dynamic behavior class, following the scheme of Wolfram's classic classification. It was then possible to predict the class of rules of a temporal evolution of an elementary rule in a more effective way than others in the literature in terms of precision and computational cost. By applying the classifier to the larger neighborhood space containing 4 cells, accuracy decreased to just over 70%. However, the classifier is still able to provide some information about the dynamics of an unknown larger space with reduced computational cost.
Article Preview
Top

Proposed as a computational model describing a replicating machine (Neumann, 1966), cellular automata (CAs) are both computational and mathematical objects that have been used as simulation models in many phenomena related to biology, physics and social sciences (Green, 1990; Smith, 1994). The structure of a cellular automaton relies on a set of cells organized as a d-dimensional regular grid, each cell being able to take on one of the states from a finite set. As a discrete dynamical system, the values of the cells change when applying their transition function (or rule) to their neighborhood, defined by the cell itself and its local vicinity, and the result of applying the function for a finite time leads to its temporal evolution (Sarkar, 2000).

The set of possible rules is a discrete space defined by all rules sharing the same characterization. A rule defines the dynamical behavior of a cellular automaton, and for each one, its typical dynamics can be obtained. Among the possible rules of each space, to delimit those of interest to simulations of some phenomena or that present a target dynamical behavior is a difficult task due to the number of possible rules in each space, which increase exponentially with the number of cells in the neighborhood. To make things worse, in general it is not possible to predict the future state of the CA without applying the rule for an arbitrary time. The possible initial configurations make the possibility by predicting the future state of the system even more difficult.

The initial configuration of the system is the configuration of its cell states. In the case of 3 states and configurations of 83 cells, for instance, there are 383 possible initial configurations, and not necessarily all of them results would yield the same dynamics. However, for most of the possible initial configurations the application of a specific rule results in typical behavior, so that the classification of the dynamical behavior of a rule always relies on the associated typical behavior of its temporal dynamics. Naturally, not all initial configurations lead to the typical behavior of the rule, which can lead to errors. It is then necessary to generate a representative set to derive the typical dynamical behavior of a rule (Wolfram, 2002).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 8: 4 Issues (2019)
Volume 7: 4 Issues (2018)
Volume 6: 2 Issues (2017)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing