The Complexity Of Time Series Generated By Cellular Automata

Cellular automata are ideal mathematical models of complex systems in nature, They can emulate lots of phenomenon in nature and life phenomena. Many unsolved questions in this difficult and interesting field show great prospect in the future.It has passed half a century since von Neumann first proposed the idea of cellular automata, scholars have made lots of research to cellular automata, however there are few efficient methods to study cellular automata, and the strict mathematical results are also few. This article explores a new kind of method to study cellular automata, in which by using distinct excluded blocks theory, computer search and symbolic dynamics to study the time series (the series generated at one site in the course of evolution) generated by 256 elementary cellular automata. Using the character of time series, we can study their evolution language (in this article without special remark the evolution language's width is always 1) by study their distinct excluded blocks, and pinpoint their Chomsky level and strict mathematical expression of the time series generated by most elementary cellular automata.After studying the time series generated by elementary cellular automata, according to the complexity of their evolution language we can classify them into four classes: I class of surjective, II class of finite complement regular languages, III class of infinite complement regular languages, and IV class which are probably unregular languages.Class â… : the cellular automata in this class have no distinct excluded blocks, their evolution languages are the largest regular languages, and for some of them the evolution languages with any width are also regular.Class â…¡: the cellular automata in this condition have finite distinct excluded blocks, and we can know their evolution languages are finite complement regular.Class â…¢: the cellular automata in this condition have infinite distinct excluded blocks. After theoretical analysis we can show that their evolution languages are regular. An example is rule 27 ECA.Class â…£: the cellular automata in this condition also have infinite distinct excluded blocks, and their evolution languages are probably not regular languages. This class is much more complex than other classes. The discussion for this class is not completed yet. In this article we prove that the evolution language of rule 56 ECAwith width 1 is context-free language, and obtain the evolution language's strict mathematical expression.