Advances in the study of elementary cellular automata regular language complexity |
| |
| Authors: | Pedro P B De Oliveira Eurico L P Ruivo Wander L Costa Fábio T Miki Victor V Trafaniuc |
| |
| Institution: | 1. Faculdade de Computa??o e Informática;2. Pós‐Gradua??o em Engenharia Elétrica e Computa??o, Universidade Presbiteriana Mackenzie, Consola??o, S?o Paulo, Brazil |
| |
| Abstract: | Cellular automata (CA) are discrete dynamical systems that, out of the fully local action of its state transition rule, are capable of generating a multitude of global patterns, from the trivial to the arbitrarily complex ones. The set of global configurations that can be obtained by iterating a one‐dimensional cellular automaton for a finite number of times can always be described by a regular language. The size of the minimum finite automaton corresponding to such a language at a given time step provides a complexity measure of the underlying rule. Here, we study the time evolution of elementary CA, in terms of such a regular language complexity. We review and expand the original results on the topic, describe an alternative method for generating the subsequent finite automata in time, and provide a method to analyze and detect patterns in the complexity growth of the rules. © 2015 Wiley Periodicals, Inc. Complexity 21: 267–279, 2016 |
| |
| Keywords: | elementary cellular automaton limit behavior regular language finite automaton process graph complexity |
|
|
