Evolution Complexity of the Elementary Cellular Automaton Rule 18
Zhi-Song Jiang
Department of Mathematics,
Suzhou University, Suzhou, China 215006
and
Physical School,
East China University of Science and Technology,
Shanghai, China 200237
Hui-Min Xie
Department of Mathematics,
Suzhou University, Suzhou, China 215006
Abstract
Cellular automata are classes of mathematical systems characterized by discreteness (in space, time, and state values), determinism, and local interaction. Using symbolic dynamical theory, we coarse-grain the temporal evolution orbits of cellular automata. By means of formal languages and automata theory, we study the evolution complexity of the elementary cellular automaton with local rule number 18 and prove that its width 1-evolution language is regular, but for every n greater than or equal to 2 its width n-evolution language is not context free but context sensitive.
