The Zoo article contains details and shows some examples.

David Eppstein's arXiv article "Searching for Spaceships" contains an excellent account of the construction and usage of de Bruijn-like diagrams, making it clear that some search programs, at least, use them, perhaps only implicitly. If one understands "brute force" search as setting up all possible bit patterns in a given region, watching their evolution, and hoping for recognizable results, then de Bruijn searches anticipate the results by trying to extend small regions already known to exhibit the desired behavior. Programming such a search is more complicated, but is guaranteed of success and should procede much faster. Of course such flagrant statements have details which can be quibbled over.

Looking over the Wiki portion of this forum or the other catalogues of Life patterns which can be found on and off the Internet, most of the patterns are grouped in families. Their existence is mostly known to Life practicioners, but their existence does not show up when the patterns are simply catalogued by live cell content; trying to give a whole Wiki page to each pattern is grossly extravagant. An avatar, together with a regular expression characterizing the family, would be more informative and produce a more concise catalog. Regular expressions are the way to characterize graphs, with their loops and all. Equivalent to regular expressions are grammars, such as those Dean Hickerson and David Bell have used to characterize their c/2 and c/3 spaceship families.

Beyond grammars, de Bruijn diagrams, as do graphs in general, have other properties which can be helpful in classify Life objects. For example, the idea of a connected component, in which every vertex can be reached from any other vertex by at least one path. Components are isolated when there is no path from any vertex in one of them to any vertex in the other. An intermediate degree if connectedness arises when there are links from one component to the other, but not in the reverse direction. This idea should be contrasted with the distinction between figures and pseudofigures in the Life classifications.

Aside from the issue of whether some figures can be joined to others, note that the existence of loops implies that the structure defined by the contents of the loop can be repeated at will, giving extensible figures. Viz: boats, long boats, really long boats, tremendously long boats, and so on. The loops correspond to the regular expression operator *, concatination follows the loop and sum makes branches in the path. What might be worth checking in the published and posted literature is whether searches have simply been used to turn up an interesting result, or whether their progress has been mapped with a view to finding families.

Turning to the Zoo article, it was not so easy to read it after two decades; conventions which were obvious at the time weren't so obvious after all. To start with, there are misprints in the table on page 3 - the entry at row ij and column k should always be jk unless it is absent (no link). The same comment evidently applies to the other tables.

The indices themselves are octal numbers referring to the occupancy of the semineighborhoods, 2 wide and three high, so the matching middle index registers an admissible overlap. The decision to include or reject a link follows some boolean property of the neighborhood; for a still life, the predicate is "the evolved cell is the same as the

original." To go further than first neighbors, larger cells ought to be chosen; for example to accomodate several generations of evolution and study shift-periodicity. The Zoo article was only interested in first (Moore) neighbors and one generation.

Whether or not one is willing to lay the diagram out on a large sheet of paper, there are reasonable matrix programs to calculate powers of the matrix: a shortest path is revealed by the first power at which the link in the power matrix deviates from zero, the main diagonal reveals closed loops - both the shortest and the multiplicity, and so on. Components result in a block matrix, and even the eigenvalues and eigenvectors may have some use. All of this gives a first stage de Bruijn diagram, but one wonders of there aren't something like two-dimensional diagrams for something akin to Wang tiles.

Life having a vacuum, zero tiles connect to themselves via a null loop. The connected component of the zero tile reveals potential freestanding configurations, since tile sequences beginning and ending on zero semineighborhoods cannot interact and can go on and on to infinity. Full loops should be chosen, since otherwise joining sequences might be ambiguous; they will lead to periodic structures (agars, most likely) at the second stage.

To get second stage tiles, a 3 high x n strip is chosen with the aid of the first level de Bruijn diagram; indeed several according to the number of distinct loops of length n in that diagram. Supposing thatthose strips have run along horizontally, the time has come to stack copies of them vertically. Their semineighborhoods are 2xn, so it is convenient to describe them by a string of hexadecimal digits taking clusters of four cells starting at the left and ending with an octal digit if the length is odd. The second stage de Bruijn diagram first of all records whether the top row of the bottom strip matches the bottom row of the top strip and so on vertically. It is then a given that the middle row behaves properly.

Again, components are to be sought, loops identified, the zero tile examined and whatever else comes to mind. If zero tiles were present at both levels, freestanding configurations can be found and enumerated. Otherwise agars will result; note that the Wiki only lists only three, but there are ever so many more.

To give a concrete example, take the width 1 still life on page 4. That is too short to make anything but a degenerate example. a column of three zeroes can be copied to maintain zeroes, but copying anything but a central 1 will overcrowd the central 1, giving the three tiles in the figure. At the second stage the zeroes stack vertically, the vertical fibres stack horizontally by periodicity and the result is pure vacuum. The middle 1 can be either at the top or the bottom of its semineighborhood, Tile 1 connects to tile 2 by overlaying the 1's, 2 connects to 1 by overlaying the 0's. Copying the alternating vertical column horizontally results in an agar, wherein rows of live cells alternate vertically with rows of inert cells.

Although this example seems rather contrived, it nevertheless illustrates the scheme which is followed for all greater widths. For example, at width 4, tiles 00, 50, F0, and A0 will make a thick column ending in two single columns of zeroes. This is the mechanism which embeds freestanding in periodic. Furthermore since these tiles are part of the second level zero component, the sequence .. 00 50 F0 A0 00 ... isolates a freestanding block. So it is possible to find all the still lifes according to given freestanding or periodic widths, and entirely arbitrary heights (depths are gotten by reading the links backwards).