The subset diagram
By its very definition, a de Bruijn diagram serves as a guide to the sequencing of strings of symbols, from which any other set of objects can be given the same sequencing. A trivial example would be to recover the original symbols from the central element of each string, while the purpose of using neighborhoods from an automaton is to obtain the sequence of evolved cells. In the same way, a de Bruijn matrix serves as a skeleton in which the rules of matrix multiplication (for noncommutative elements) ensures that the elements of a product respect the sequence of the corresponding de Bruijn diagram.
In this spirit, alternative labels can be affixed to the links in a de Bruijn diagram; reading one label instead of the other while following along some path associates the labels with one another. In particular, relating the central cell of a neighborhood to the value of the evolved cell associates configurations with their ancestors; whether or not there was any ancestor at all turns into the question of discovering whether the corresponding path exists somewhere in the diagram.
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx