Intro Soup Recipe Shelf Sink Chef
Take me higher...

LwoD References

[1] D. Bell, Max, http://www.cs.jhu..edu/~callahan/patterns/max.html.

[2] A. Condon, A theory of strict P-completeness. STACS 1992, in Lecture Notes in Computer Science 577 (1992) 33 - 44.

[3] R. Fisch and D. Griffeath, WinCA: a cellular automaton modeling environment. Windows 3.x/95 software, version 1.0, 1996. Available from [7].

[4] E. Fredkin and T. Toffoli, Conservative logic. Int. J. Theor. Phys. 21 (1982) 219 - 253.

[5] J. Gravner and D. Griffeath, Cellular automaton growth on Z2: theorems, examples, and open problems. In preparation.

[6] R. Greenlaw, H.J. Hoover, and W.L. Ruzzo, Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, 1995.

[7] D. Griffeath. Primordial Soup Kitchen, http://math.wisc.edu/kitchen.html.

[8] Jörg Heitkötter, Zooland}, http://www.krl.caltech.edu/~brown/alife/zooland/.

[9] K. Lindgren and M.G. Nordahl, Universal Computation in Simple One-Dimensional Cellular Automata. Complex Systems 4 (1990) 299 - 318.

[10] J. Machta and R. Greenlaw, The computational complexity of generating random fractals. J. Stat. Phys. 82 (1996) 1299.

[11] C. Moore, Quasi-linear cellular automata. Santa Fe Institute Working Paper 95-09-078, to appear in Physica D, Proceedings of the International Workshop on Lattice Dynamics.

[12] C. Moore, Non-Abelian cellular automata, Santa Fe Institute Working Paper 95-09-081, Predicting non-linear cellular automata quickly by decomposing them into linear ones, submitted to Physica D.

[13] C. Moore, Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness. Santa Fe Institute Working Paper 96-08-060, to appear in J. Stat. Phys.

[14] C. Moore and M.G. Nordahl, Lattice Gas Prediction is P-complete. Santa Fe Institute Working Paper 97-04-034, available as comp-gas/9704001.

[15] C. Moore, The computational complexity of sandpiles. In preparation.

[16] N. Packard and S. Wolfram, Two-dimensional cellular automata. J. Stat. Phys. 38 (1985) 901 - 946, and private communication.

[17] C.H. Papadimitriou, Computational Complexity. Addison-Wesley, 1994.

Acknowledgments. We thank Janko Gravner for help with the LwoD figures and Dean Hickerson for expertise on the behavior of LwoD's relatives. We also thank Rascal, Scurry, Oscar and Spootie for companionship and inspiration.

Back

Take me higher...
Intro Soup Recipe Shelf Sink Chef