Diagrama de Bruijn

Los nodos del diagrama de Bruijn son secuencias de símbolos de algún alfabeto, justo como en las expresiones regulares. Las ligas del diagrama describen la manera en la cual tales secuencias pueden superponerse. Diferentes grados de superposición llevan a diferentes diagramas. En el diagrama básico, la superposición consta de un símbolo inicial, un símbolo que relaciona las secuencias y un símbolo terminal.

Cuando los símbolos que representan los estados del autómata celular son enteros, la faci-lidad de tratar sus propiedades aritméticamente o algebráicamente motiva a la utilización de esta herramienta. Por ejemplo, la ecuación que define a la matriz topológica de un diagrama de Bruijn es:

$$MB_{i,j} = \left \{ \begin{array}{ll} 1&j = \left \{ \beg... ...\ \\ 0&\mbox{en cualquier otro caso} \end{array} \right .$$ (3.2)

donde $k$ representa el número de estados y $r$ el radio de vecindad. La variable $i$, la cual representa el renglón de la matriz va a tomar valores desde $0$ hasta $\char93 (N) - 1$, mientras que la variable $j$, la cual representa la columna de la matriz tomará valores de acuerdo a los valores que tengan $k$, $i$ y $r$ (para algunos casos). Así pues, para un autómata celular lineal (2,1) los valores de $i$ y de $j$ se generan de la siguiente manera: si $i=0$ entonces $j$ va a tomar valores a partir de las operaciones $2(0)$ y $2(0)+1$, por lo tanto en este caso $j$ toma los valores $0$ y $1$ respectivamente. Si $i=1$ entonces $j=2(1)=2$ y $j=2(1)+1=3$. Si $i=2$ entonces $j=2(2)=4$ módulo $4=0$ y $j=2(2)+1=5$ módulo $4=1$. Si $i=3$ entonces $j=2(3)=6$ módulo $4=2$ y $j=2(3)+1=7$ módulo $4=3$. La matriz topológica de Bruijn MB que se obtiene a partir de la ecuación 3.2 es la siguiente:

$$MB = \left ( \begin{array}{cccc} 1_{00} & 1_{01} & 0_{02... ...\ 0_{30} & 0_{31} & 1_{32} & 1_{33} \end{array} \right )$$

Cabe mencionar que los valores de $i$ van de $0$ a $3$ debido a que la cardinalidad del conjunto $N$ (la cual está determinada por $k^{2r}$) es $4$ puesto que $4$ nodos pueden representar todas las vecindades posibles de tres células para un autómata celular lineal (2,1). En la figura 3.23 se observan estas vecindades, las cuales se obtienen de la siguiente forma: consideremos el nodo con la etiqueta $00$ y el nodo con la etiqueta $01$; para que exista una liga entre ambos, debe coincidir el último símbolo del nodo que se considera de partida con el primer símbolo del nodo que se considera de llegada. En este caso si tomamos el nodo $00$ como nodo de partida y el nodo $01$ como nodo de llegada, podremos verificar que el símbolo $0$ enlaza a los dos nodos y por lo tanto puede existir una liga que conecte al nodo $00$ con el nodo $01$. En el caso contrario, es decir, si se toma el nodo $01$ como nodo de partida y el nodo $00$ como nodo de llegada, no podrá existir una liga de enlace entre ambos nodos puesto que el último símbolo del nodo de partida no coincide con el primer síimbolo del nodo de llegada. Esta misma verificación se realiza para todos los nodos del diagrama para establecer todas las ligas posibles. Cabe mencionar que las etiquetas de los nodos del diagrama de Bruijn genérico para un autómata celular lineal (2,1) son símbolos que forman vecindades parciales. Para el caso genérico, las vecindades parciales de dos células forman una vecindad completa de tres células al superponer el símbolo que establece la liga entre dos nodos. En todo diagrama de Bruijn los nodos están etiquetados con vecindades parciales las cuales están conformadas por un número par de células. En el siguiente capítulo analizaremos diagramas de Bruijn con vecindades parciales de más de dos células.

Figura 3.23: Diagramas de Bruijn genéricos para un autómata celular lineal (2,1). En el diagrama del lado izquierda (a) las vecindades parciales están expresadas en notación binaria, mientras que en el diagrama del lado derecho (b) están en notación decimal.

En la figura 3.24 se muestra el diagrama de Bruijn de la regla 54. En ésta se ilustran las ligas que producen cada una de las ocho vecindades y se resaltan con color negro aquellas en las cuales sus respectivas células centrales evolucionan al estado 1.

Figura 3.24: Diagrama de Bruijn de la regla 54.