PATTERN GROWTH IN ELEMENTARY CELLULAR-AUTOMATA

A classification of elementary cellular automata (CA) based on their p attern growth is introduced. It is shown that this classification is e ffective, that is, there exists an algorithm to determine to which cla ss a given CA belongs. This algorithm is based on the properties of th e local rule of CAs, not requiring the observation of their evolution. Furthermore, necessary and sufficient conditions to detect all the el ementary CAs exhibiting a shift-like behavior are given; these CAs hav e interesting dynamical properties and chaotic characteristics.