On the reduction of computational complexity of cellular automata

The computational complexity of cellular automata (CA) is investigated. Using unified approach to the CA behavior, we define the notion of CA convergence and propose the measures of the time and space complexity. The approach to the complexity reduction for some classes of synchronous CA is discussed. Then we consider the counterexample that shows that our reduction methods are not, in general, applicable to asynchronous models of CA.