Diagrama de de Bruijn

Los orígenes del diagrama de de Bruijn se encuentran en trabajos orientados al estudio de registros de corrimientos de una secuencia de símbolos para la codificación de información, el nombre de este diagramas se debe a los trabajos hechos por N. G. de Bruijn [McIntosh 91a] y por Solomon W. Golomb [Golomb 67].

El uso del diagrama de de Bruijn en autómatas celulares es de gran importancia ya que puede representar de una manera natural y conveniente la evolución de las vecindades de un autómata celular lineal. Cada nodo del diagrama de de Bruijn representa un conjunto de $2r$ células, entonces tendremos tantos nodos como $k^{2r}$.

Estos nodos funcionan como vecindades parciales del autómata; las ligas van a partir de un nodo a otro si los ultimos $2r-1$ elementos del nodo inicial concuerdan con los primeros $2r-1$ elementos del nodo final, la liga representará una vecindad completa compuesta por la secuencia formada por el nodo inicial y el nodo final traslapando en $2r-1$ elementos; por lo tanto tendremos tantas ligas como vecindades posibles distintas haya en el autómata, es decir $k^{2r+1}$. La etiqueta o el color de la liga nos representa el estado que surge de la evolución del autómata. Por supuesto, hay que tener en cuenta que mientras mayor sea el número de estados y/o el tamaño de vecindad, también crece el número de nodos y de ligas del diagrama de de Bruijn lo que trae consigo problemas de representación gráfica.

Como toda gráfica, el diagrama de de Bruijn tiene una representación matricial asociada, a la cual se le conoce como matriz de evolución. La importancia del diagrama de de Bruijn es que nos dá una forma de representar graficamente la regla de evolución, por ejemplo, una aplicación sencilla podría ser recobrar todos los ancestros que forman una cadena dada con solo hacer un registro de todos los caminos distintos que tienen la forma de la cadena deseada.