Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Middle school? The StackExchange terms of service require you to be 13 or older. –  Qiaochu Yuan Jul 19 '12 at 20:27
    
I am 13. Also, Eppstein's paper is right here: arxiv.org/abs/cs/0004003 –  Darius Goad Jul 19 '12 at 20:32
1  
I still don't get why so many people think age is such a good measure of maturity, when really, it's the worst out there... –  Darius Goad Jul 19 '12 at 20:38
3  
@Qiaochu: He waited until now to post something! :-P –  Asaf Karagila Jul 19 '12 at 20:49
1  
@DariusGoad - there are different kinds of maturity, some of which (like physical maturity) are more highly correlated with age than others. Correlation, of course, does not exclude the possibility of infrequent cases which appear to contradict a dominant relationship between factors. –  Mark Bennet Jul 19 '12 at 20:59

1 Answer 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.

share|improve this answer
    
Thank you. This was not the entirety of what I was looking for, but at least it's a start. –  Darius Goad Jul 20 '12 at 21:19
    
Now I've looked at Eppstein's paper, I'm not sure there's a relation between the graphs I've described and the ones he's talking about. Did you notice that when he starts to discuss deBruijn graphs, he gives a couple of references, [16] and [17] - did you follow up on those? –  Gerry Myerson Jul 21 '12 at 9:46
    
No, I'll try and see what he's talking about. –  Darius Goad Jul 21 '12 at 17:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.