  Elementary cellular automata (ECA) are one-dimensional discrete models of
computation with a small memory set that have gained significant interest since
the pioneer work of Stephen Wolfram, who studied them as time-discrete
dynamical systems. Each of the 256 ECA is labeled as rule $X$, where $X$ is an
integer between $0$ and $255$. An important property, that is usually
overlooked in computational studies, is that the composition of any two
one-dimensional cellular automata is again a one-dimensional cellular
automaton. In this chapter, we begin a systematic study of the composition of
ECA. Intuitively speaking, we shall consider that rule $X$ has low complexity
if the compositions $X \circ Y$ and $Y \circ X$ have small minimal memory sets,
for many rules $Y$. Hence, we propose a new classification of ECA based on the
compositions among them. We also describe all semigroups of ECA (i.e.,
composition-closed sets of ECA) and analyze their basic structure from the
perspective of semigroup theory. In particular, we determine that the largest
semigroups of ECA have $9$ elements, and have a subsemigroup of order $8$ that
is $\mathcal{R}$-trivial, property which has been recently used to define
random walks and Markov chains over semigroups.
