Complexity in Cellular Automata

In order to identify complex systems capable of modeling artificial life, we study the notion of complexity within a class of dynamical systems called cellu- lar automata. We present a novel classification of cellular automata dynamics, which helps us identify interesting behavior in large automaton spaces. We give a detailed comparison of our results to previous methods of dynamics classification. In the second part of the thesis, we study the backward dynamics of cellular au- tomata. We present a novel representation of one-dimensional cellular automata, which can be used to charcterize all their garden of eden configurations. We demonstrate the usefulness of this method on examples.