2
$\begingroup$

I've been looking at a program gfind, that searches for spaceships in Conway's Game of Life. The documentation says a bunch of stuff about searching De-Bruijin graphs. I couldn't find any useful information about these on the internet, I couldn't figure out how they could be searched, and I'm too broke to get a book. I also looked through David Eppstein's paper [1] on the matter, but it still was too cryptic. I just need an explanation at a high-school level (even though I'm in middle school O_O) of how the algorithm works.

[1] Searching for Spaceships, David Eppstein http://arxiv.org/abs/cs/0004003

  • 1
    @Darius: age isn't a good measure of maturity, but it's much easier to measure than anything else you could care to name, so it's much easier to make policies and write legal documents about. My understanding is that there are laws about young people using the internet and StackExchange could possibly get into legal trouble (if not now then possibly at some point in the future) if they didn't have an age policy. There are other concerns here than just whether age is a good measure of maturity.2012-07-19

1 Answers 1

1

I don't know about the search algorithms, but here's an example of a deBruijn sequence: $1110100011$ It has the property that if you read off all the runs of three consecutive symbols, you get $111\quad110\quad101\quad010\quad100\quad000\quad001\quad011$ which is to say you get all possible triples of symbols. More generally, a deBruijn sequence of order $k$ for a language of $s$ symbols is a string of symbols from an alphabet of $s$ symbols such that the runs of $k$ consecutive symbols give you all possible strings of $k$ symbols from that alphabet.

Graphs come into it the following way (by the way, these are the graphs studied in combinatorics, not the graphs studied in analytic geometry): make a graph whose vertices are all the strings of $k-1$ symbols (so, in our example, the vertices are 00, 01, 10, and 11), and have an edge with the label $x$ join two vertices if you can get from the one vertex to the other by putting $x$ at the end and deleting the first symbol. For example, you can get from 01 to 10 by putting a 0 at the end of 01 and then deleting the 0 at the beginning, so you draw an edge from 01 to 10 and label it 0; you can get from 01 to 11 by putting a 1 at the end and deleting the 0 from the beginning, so there's an edge from 01 to 11 labeled 1. Note there's an edge from 00 to itself, labeled 0, and one from 11 to itself, labeled 1.

Now you can prove that the graph you get is Eulerian, which means there's a way to start at any vertex and travel around the graph, using every edge exactly once. In our example, starting at 11, you can use edges labeled 1, 0, 1, 0, 0, 0, 1, 1 to do this. Now notice that if we put together the starting 11 with that sequence of edges we get exactly 1110100011, our deBruijn sequence.

Well, you always get deBruijn sequences this way, so you can call the graph a deBruijn graph.

  • 0
    No, I'll try and see what he's talking about.2012-07-21