Diagrama de de Bruijn

Un paso acostumbrado en dinámica simbólica es repre-sentar un corrimiento de tipo finito por medio de una gráfica , donde todas las posibles rutas del diagrama muestren la colección de las secuencias que se tienen en $\mathcal{C}_{\begin{picture}(5,5)(0,0) \put(0,0){\mbox{\tiny $\mathfrak{P}$}} \put(0,0){\mbox{\small $\times$}} \end{picture}}$, para autómatas celulares lineales, la gráfica que resulta natural para conocer las evoluciones del conjunto $\mathcal{C}$ es el diagrama de de Bruijn [McI91].

Para un autómata celular con $k$ estados y un radio de vecindad $r$, la definición del diagrama de de Bruijn es la siguiente:

• El conjunto de nodos del diagrama de de Bruijn $\mathcal{N}_{B}$ consistirá de todas las posibles secuencias de estados de longitud $2r$, es decir, $\mathcal{N}_{B}=K^{2r}$.
• Para $\mathrm{n}_i, \mathrm{n}_j \in \mathcal{N}_{B}$, existirá una arista de $\mathrm{n}_i$ a $\mathrm{n}_j$ si los $2r-1$ elementos finales de $\mathrm{n}_i$ son iguales a los $2r-1$ elementos iniciales de $\mathrm{n}_j$, para el caso en que $r=1/2$, tenemos 0 elementos finales para $\mathrm{n}_i$ y 0 elementos iniciales para $\mathrm{n}_j$, por lo que en esta situación en particular el diagrama será completo.
• Cada arista en el diagrama de de Bruijn representa una vecindad del autómata, es decir, un bloque de estados de longitud $2r+1$, tomando en cuenta el elemento inicial del nodo $\mathrm{n}_i$, el traslape de longitud $2r-1$ y el elemento final del nodo $\mathrm{n}_j$. Al conjunto de aristas del diagrama de de Bruijn se le denominará con $\mathcal{A}_{B}$ y representa al conjunto de vecindades $K^{2r+1}$ de un autómata celular lineal.
• Cada arista $a \in \mathcal{A}_{B}$ se etiquetará con un símbolo o se coloreará con un color distinguiendo el estado en el cual evoluciona la vecindad representada por $a$, o sea, el etiquetado de todas las aristas representa al mapeo
  $\phi:K^{2r+1} \rightarrow K$ que es la regla de evolución del autómata.

Figura 12: Diagramas de de Bruijn genéricos.

Por medio del diagrama de de Bruijn, tenemos una re-presentación gráfica de la regla de evolución, las rutas en este diagrama representan todas las posibles configuraciones que aparecen en la evolución del autómata celular como producto de $\phi$.

Cabe señalar que en la literatura sobre dinámica simbólica, el uso del diagrama de de Bruijn es casi inexis-tente, prefiriendo usar otro tipo de diagramas más a la manera de la representación gráfica de autómatas finitos, o la gráfica dual del diagrama de de Bruijn (en caso de existir).