Advances in the study of elementary cellular automata regular language complexity. Issue 6 (6th May 2015)

• Record Type: Journal Article
• Authors: De Oliveira, Pedro P. B.; Ruivo, Eurico L. P.; Costa, Wander L.; Miki, Fábio T.; Trafaniuc, Victor V.
• Is Part Of: Complexity. Volume 21:Issue 6(2016)
• Page Start: 267
• Page End: 279
• Publication Date: 2015-05-06
• Subjects: elementary cellular automaton -- limit behavior -- regular language -- finite automaton -- process graph -- complexity; Chaotic behavior in systems -- Periodicals; Complexity (Philosophy) -- Periodicals; 003
• DOI: 10.1002/cplx.21686
• Languages: English
• ISSNs: 1076-2787

Abstract

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