A stochastic multi-state cellular automata model and its application in scheduling and density classification problems

Abstract

Cellular automata (CA) consist of identical components (cells), which change states through time according to a transition rule that considers local information. CA are very simple but possess an impressive computing capacity and present complex behaviour. CA are applied to various applications, such as simulation of natural phenomena or for performing a specific task. The central CA component is the rule that govern the change in cell states. This rule can be manually designed for a specific problem or discovered through search methods. However, as the number of states in the cells increases (in the case of multi-state CA), the size and complexity of the rule grow exponentially, which makes CA employment difficult. As a solution to this difficulty, this thesis proposes the ‘Stochastic CA with Reduce and Mapping' (SCA-RM), a model in which the size of CA rules remains unchanged, regardless of the number of states. This is achieved through the use of three key components in the proposed CA: (I) Reduce, which converts any configuration of states into two states (binary); (II) A traditional CA rule that operates with only two states; (III) Mapping, which translates the output state from the binary rule into an arbitrary state chosen from the original applications set of states. As a consequence, proposed model rules are much simpler than traditional CA rules. Initially, we employed this model to task scheduling, and the results indicate that the proposed CA significantly outperforms the state-of-the-art solutions based on traditional and totalistic CAs. This result is due to the efficient simplification of CA rules provided by SCA-RM. Next, when tested in the multi-state density classification problem, SCA-RM significantly outperforms the traditional CA model. Therefore, results strongly support SCA-RM as the best solution for addressing multi-state CA applications. By simplifying CA rules, SCA-RM opens up new possibilities for the application of cellular automata in a wide range of applications involving many states.