El estudio de las autómatas celulares comenzó cuando John von Neumann se interesó en la posibilidad de construir máquinas que pudieran autoreproducirse. La teoría de autómatas celulares se basa en una regla de evolución que se aplica a una grupo de células, la regla de evolución nos indica en que evoluciona cada grupo de celulas, es necesario mencionar que cada grupo de células evoluciona en una sola celula a la cual se le llama mapeo, al conjunto de posibles estados que puede tener una célula se le denomina K; al grupo de células al cual se le aplica la regla de evolución se le llama vecindad y la cantidad de células que puede tener una vecindad esta en relación al número de vecinos que tiene a cada lado la célula central a este numero se le llama R, entonces en tamaño de la vecindad es 2R + 1 y el número de vecindades será
porque cada celula de una vecindad puede tener K estados, si hay
vecindades cada una de estas puede evolucionar en K estados lo que nos da
posibles reglas de evolución.
La teoría de gráficas juega un papel importante en los autómatas celulares porque podemos representar gráficamente la evoluci'on y describir algunas propiedades locales y relacionarlas a propiedades globales.[1]
Se mencionó que cada vecindad evoluciona en una sola célula, por lo que para encontrar la siguiente evolución completa es necesario que las vecindades traslapen.
Observar tal traslape a simple vista es un tanto confuso, pero es posible representarlo mediante gráficas que se utilizaron en primera instancia en la teoría de registros de corrimiento, en donde también se observan traslapes, tales gráficas son los diagramas de de Bruijn.[1]