Cellular Automata FAQ


[Non-Java version]

Applications

Collapse all tree nodesExpand all tree nodes
Expand this node
Expand/collapse
Expand this node
Can CA be used to do image processing?

Contributions by:

<shinbrot@bart.chem-eng.nwu.edu> Troy Shinbrot Pawel Siwak <PSIW@agat.kari.poz.edu.pl>

You may try:

K.Preston, M.J.B.Duff - Modern Cellular Automata. Theory and Applications. Plenum Press, London, 1984.

There was a good article in Physica D, N10

Look also for work referencing "systolic array"

Look at the MIT server

For something closely related, you might want to contact Deliang Wang at the Ohio State University, who has written a paper, "Global competition and local cooperation in a network of neural oscillators," which describes an attractive dynamical mechanism involved in pattern recognition. It is not a CA, but it is very close and could without much difficulty be converted to a CA.

For applications of genetic algorithms to image processing see: GA Image

Expand this node
Expand/collapse
Expand this node
Are there any CA models of urban development?
Contributions by:
  • Michael Batty <GEOBATTY@ubvms.cc.buffalo.edu>
  • Holger Doernemann <doerne@lusty.informatik.uni-dortmund.de>
  • Jeffrey M. Field <jfield@netcom.com>
  • Michel T. Talbot <bo964@FreeNet.Carleton.CA>

Cellular models in Geographical Information Systems: [SOB92]. The book uses the field of urban geography as a practical example for point-in-cell methods of spatial subdivision and analysis. For example, chapter 8 "Point Pattern Analysis" describes the use of cellular models for Nearest Neighbour analysis in: -Voronoi diagram of distribution of settlements in an area of Montana -Location of robberies in Milwaukee area vs location of victims' addresses -Voronoi cellular diagram of Japanese black pine saplings -The distribution of appartment buildings vs streets in Kohto-Sumida,Tokyo

also check out: urban refs urban paper

References

[WEU00] [WE00] [BL94] [DBG93] [Ita88]

Expand this node
Expand/collapse
Expand this node
Have CA been used to model ant behavior?

Contributions by:

Bauchau, Vincent" <bauchau@cto.nioo.nl> Perry Wagle <wagle@cs.indiana.edu>

Most models of ants (and other social insects) are not strictly CA since the rules of behavior are associated with elements that move, rather than with a site in space. However, there are many basic questions ("How do simple local rules give rise to global complex behavior?") which apply equally well to CA and ant models.

The definitive book on ants is: Wilson E.O. and Holldobler B 1990 The Ants. Springer, 732 pp, 1000 ill. (This book won the Pullitzer price.)

"A Parallel Distributed Model of the Behaviour of Ant Colonies" D.M. Gordon, B.C. Goodwin and L.E.H. Trainor, J theor Biol (1992) 156, 293-307. Models the dynamics of task-switching in harvester ants.

Expand this node
Expand/collapse
Expand this node
What computations can CA do?

Contributions by: Benedict.M.Wightman@cm.cf.ac.uk

If you just want a CA that does !gates then 'Wireworld', a CA that simulates 'electron streams' is probably an easier starting point than Conway's Life that exhibits the same level of computational complexity, just on a more manageable scale. It's in the CA Lab (Rudy Rucker's PC-based CA package), but the rules are fairly simple and it may well be elsewhere too.

Cellular-3.0 includes WireWorld as an example. WireWorld example

See wireworld

Expand this node
Expand/collapse
Expand this node
Can CA be used to model ecological systems?

Contributions by: Matthew Burke <burke@delta.math.wsu.edu> Marimar Villagarcia <MARIMAR@dma.ulpgc.es>

Recently there has been a significant increase in the number of articles that deal with cellular automata (CA) and ecological modeling. There are also several questions on how various aspects of CA affect their usefulness in ecological models. What follows are some quick thoughts on where the major difficulties with CA and ecological models lie. It is not intended to be thorough, and it is not as well argued as I'd like. At the end is a list of interesting references in the area.

The major question that needs to be addressed is that of CA's synchronicity. [Hog88], and others, have claimed that the simultaneous updating of all cells is at odds with the localness of interaction that is one of the strengths of CA. It has been shown that changing the definition of a CA to allow for asynchronous updating of cells can dramatically alter the behavior of the CA [Hog88] [HG93]. In particular, frequently the interesting structure seen in the evolution of a CA is, in fact, an artifact of the synchronous updating.

What needs to be addressed is whether or not there are ecological systems for which universal updating is not an unwarranted assumption. For example, [SHJD92] develop a CA model of competition between grass species. I have not yet researched the characteristics of the species involved in their model, but it is not inconceivable to think that the dynamics of a set of annual plants may be modeled synchronously (perhaps the species all germinate at close enough times that on the scale of a year, we can think of it as synchronous).

On the other hand, [Gre90] develops a CA model of the effects of fire and dispersal on spatial patterns in forests. I see no a priori reason, however, to assume that synchronous updating is reasonable in this situation.

Another issue that needs to be investigated is the problems associated with multiple scales, both spatial and temporal. Typically CA models are developed with the assumption that a cell is a physcial region of the right size for one (or, perhaps, a few) individuals. Consider a model of plankton in the Celtic Sea (I have, which is why I bring it up). If we assume that over a certain horizontal distance, conditions are homogeneous, it suffices to limit ourselves to a water column, i.e. we only need one spatial dimension. At typical concentrations (private communication with R.A. Parker) we have enough plankton that it is impractical to assume one plankton (or a few) per cell. Now the relevant scales for the diffusion of plankton nutrients (such as nitrate) is even smaller. Also, consider three typical organisms: cyanobacteria, flagellates, diatoms, and copepods. The ratio of the fastest sinking rate to the slowest is 200:1. Thus, if we use this information to scale spatially or temporally, we also run into difficulties (again, the temporal scale of diffusion for nutrients is smaller still).

Are these problems insurmountable? Is this even the best way to begin thinking about such a model? I don't have the answers. Finally, are there systems with inherent action-at-a-distance? Returning to the plankton model mentioned above, we note that during chlorophyll maxima (blooms of plankton) it is not uncommon for the plankton near the surface to dramatically decrease the amount of light to plankton at depth due to shading. Thus, we have an effect that (rapidly) is felt at great distance. Is this incompatible with the CA methodology?

Below is a list of ecologically-related papers that use CA models.

References

[DS92] [EEK93] [GNH85] [Gre82] [Gre90] [Hog88] [HH90] [HG93] [NM92] [SHJD92] [Sat89],[Sat90]

Expand this node
Expand/collapse
Expand this node
Can CA be used to model reaction-diffusion systems?

Contributions by: Joerg Richard Weimar <jweimar@ulb.ac.be>

I have developed a method for constructing a CA for reaction-diffusion equations. It basically relies on large square neighborhoods for the diffusion part and a discretization of phase space combined with (mostly probabilistic) state transition tables derived directly from the nonlinear reaction-diffusion equation. I simulate excitable media (chemical waves), pattern formation, non-conservative phase transitions, and many less spectacular RD-systems.

see also: RD talk.

Expand this node
Expand/collapse
Expand this node
Can the universe be considered to be a CA?

Contributions by: Chris Langton cgl@t13.Lanl.GOV

There is a great collection of papers [unk82]. These are the proceedings of a conference on the Physics of Computation and Computational models of Physics.

They contain some classic papers, including many that view the universe as a CA. Authors include Toffoli, Fredkin, Bennett, Landauer, Hillis, Feynman, Wheeler, and so forth.

There is a fascinating paper by Marvin Minsky entitled ``Cellular Vacuum'' in which he shows that a version of relativity holds in CA's as clocks (oscillators) approach the speed of light - they slow down, but not in the same way that they do in continuous space.

All in all, this collection is a must for those interested in computational aspects of the physical universe or in the physics of computation.

Expand this node
Expand/collapse
Expand this node
Can CA be used to encrypt messages?
Expand this node
Expand/collapse
Expand this node
What is the CAM-Brain project?
Contributions by:
  • Hugo de Garis degaris@hip.atr.co.jp

see: CAM-Brain.

Expand this node
Expand/collapse
Expand this node
What do CA have to do with deformable materials?

Contributions by:

David Ardell <ardell@charles.stanford.edu> Bruce M. Boghosian <bruceb@bu.edu>

B. Ostrovsky and M.A. Smith and Y. Bar-Yam", "Applications of parallel computing to biological problems" Ann. Rev. Biophys. Biomol. Struct. (1995) 24:239-67 - uses Margolus dynamics to conserve mass and implement excluded volume, or a novel two-space algorithm to do the same, discusses fine- vs. course-grain simulation issues

and

S. Rasmussen and J.R. Smith, "Lattice Polymer Automata" Ber. Bunsenges. Phys. Chem. (1994) 98(9):1185-1193 - extension of LGA that uses particle-interactions to implement excluded volume and polymeric bonds

There are further references within these two. The first is particularly easy to find in a good biology library. The second may not be so easy. Try contacting:

VCH Verlagsgesellschaft mbH, D-69451 Weinheim Paper #0005-9021/94/0909-1185

Also, for the modeling of microemulsions with lattice gases, see B.M. Boghosian, P.V. Coveney, A.N. Emerton, "A Lattice-Gas Model of Microemulsions,". You can obtain the paper by sending mail to comp-gas@xyz.lanl.gov with the words "get 9507001" (no quotes) in the subject line, or via the World Wide Web at: http://xxx.lanl.gov/abs/comp-gas/9507001

Microemulsions consist of two immiscible fluids (e.g., oil and water) plus a surfactant or amphiphile (e.g., detergent). The surfactant usually has a hydrophyllic ionic head, and a hydrophobic hydrocarbon tail, so that it likes to live at the oil/water interface. Depending on the relative concentrations of the three components, the mesoscale behavior of microemulsions can be exceedingly complex, as structures self-organize in order to provide sufficient surface area to accomodate the surfactant. (Not exactly deformable, but a very interesting material nevertheless.)

Expand this node
Expand/collapse
Expand this node
What are kinetic CA?

Contributions by: Joseph J. Strout <strout@helmholtz> http://www.cit.gu.edu.au/~sosic/index.html

When Von Neumann started working on robotic self-replication, he first tried the "robot in a warehouse of spare-parts" approach, otherwise known as the kinematic approach. But it was was mathematically too unweildy, so he invented CA. I wonder if there has been any serious theoretical work making CA more kinetic.

Last year I developed a simulation I called "Biomatrix" which sounds similar to what you're asking about. Cells in the matrix could have a variety of states, divided into three general categories: empty, structural unit, or instruction. Cells could also contain a "program

You might want to have a look at our paper: R. Sosic and Robert R. Johnson. Computational Properties of Self-Reproducing Growing Automata. (to appear in BioSystems)

The paper is available from: living living, ftp.

Expand this node
Expand/collapse
Expand this node
Are CA really responsible for patterns on shells?

Contributions by: arjen@fwi.uva.nl (Arjen Schoneveld) Pawel Siwak

The latest American Scientist (May-June 1995) has a cover story on 1-D CA patterns found on shells (such as Oliva porphyria and Cymbiola innexa Reeve).

Try the following book by Hans Meinhardt: "The Algorithmic Beauty of Sea Shells" ISBN 3-540-67842-0 ISBN 0-387-57842-0 Springer Verlag, 1995

G.T.Herman, G.Rozenberg - Developmental Systems and Languages. North-Holland, 1975:

In the book you'll find may be the first biologically oriented applications of cellular automata. This study of synchronization aspects of growing filaments is very interesting. There are also some shell patterns in the book, firing squad synchronization problem description, French flag problem solution, and many other topics on cellular automata and their biological context.

Expand this node
Expand/collapse
Expand this node
What do CA have to do with biological computation?

Contributions by: <altenbur@plains.NoDak.edu> (Karl Altenburg)

Two good references for molecular and biomolecular computing are:

IEEE Egineering in Medicine and Biology, February-March, 1994.

IEEE Computer, volume 25, number 11, November, 1992.

In both of these magazines there are many articles on this topic with references or pointers to many others.

Of particular interest to this group may be:

Hameroff, S.R., J.E. Dayhoff, R. Lahoz-Beltra, A.V. Samsonovich and S. Rasmussen. 1992. Conformational automata in the cytoskeleton. Computer, 25(11):30-40.

Expand this node
Expand/collapse
Expand this node
Can CA be used to construct random number generators?

Contributions by: Nelson Minar <nelson@santafe.edu>

See: nelson including a README.html, a bibliography, and lots of code.

As for a quick summary.. there are two basic classes of generators in common use. Both classes have some theoretical grounding

Linear Congruential Generator Lagged fibonacci

LCGs have a lot of history and are the root of most random number libraries. As long as the modulus m is prime and a is chosen carefully, they seem to do fairly well. But many implementations choose m to be some power of 2, which result in low order bits with extremely low periods. The particular generator of this class I use is I have an article by Park and Miller in my bibliography about this generator: it's period is .

Lagged Fibonacci generators are also fairly old, but are not as well known. Knuth deprecates them for lack of theory, but that doesn't seem entirely fair to me based on what I've read. Many choices of the function f have been suggested, usually very simple and fast ones. The one I use is based on a recent recommendation by Marsaglia: where "carry" is from the previous calculation. The Marsaglia paper in my bibliography has a nice bit of theory on this generator: it's period is roughly .

There are other methods of generating random numbers. Numerical Recipies recommends using a shuffling algorithm to mix up the output of one of these simple generators. Several researchers here recommended that method to me.

Also, a lot of cryptographic research can be thought of as a search for the perfect random number generator. Several good ones have been found: DES, for instance, is great at generating random numbers. It's also pretty slow and weighty, though.

See:

1) Tsalides Ph., York T.A., Thanailakis A. Pseudorandom number generators for VLSI systems based on linear cellular automata. IEE Proceedings-E, vol. 138, No.4, July 1991, pp. 241-249.

Expand this node
Expand/collapse
Expand this node
What links are there between CA and complexity theory?

See: Juris Hartmanis. On the Computing Paradigm and Computational Complexity. MFCS'95. (eds.) J.Wiederman, P.Hajek. Berlin, Springer 1995, LNCS No.969, pp. 82- 92.

In this paper you will find an overview of the state of affairs in computational complexity theory. Note that the author is probably No.1 world authority in the subject. The paper includes also an interesting disscussion of recent Adleman's molecular solution of the Hamiltonian path problem. The conclusion is that even molecular computations can not escape the exponential curse. The weight of "soup" becomes prohibitive. The calculations show that for a graph with 200 nodes the biologically encoded set of paths will weight more than the Earth ! The exponential function grows too fast and even atoms are a bit too heavy to break this barrier.

There is also another worthwhile paper:

3) Paul Vitanyi Physics and the New Computation MFCS'95. (eds.) J.Wiedermann, P.Hajek. Berlin, Springer 1995, LNCS 969, pp. 106-128.

It discusses the physical limits for doing computations: the geometry of space and speed of light, energy dissipation by laws of thermodynamics and quantum mechancis constraints.

Expand this node
Expand/collapse
Expand this node
What is the relationship between CA and neural networks?
There is some litterature about this:

1) Preston K, Duff M., Modern cellular automata, advanced applications in pattern recognition, New York, Plenum, pp317-328, 1984.

2) Terrier V. Real time recognition with cellular automata a meaningful example,Rapport LIP-R-90-17,ENS Lyon 1987.

3) de Lassus H, Neural network clusters and cellular automata for the detection and classification of overlapping transient signals on radio astronomy spectrograms from spacecraft. IEEE Conference on time frequency analysis Paris June 1996. (Accepted Paper).

Expand this node
Expand/collapse
Expand this node
What are Byl's rules for a self reproducing CA?

Contributions by: <hhchou@cs.umd.edu> H.H. Chou

Our research group have dealt with old self-replicating loops a while ago. I don't have time to recapture my memory, but from a quick grep search on our old rule sets archive I have found these rules which I believe implements Byl's self-replicating rule set. I don't remember if it is the "newly updated" rule set what you want, but I do know that these rules run well under our simulation environment since they are taking from executable CA rules directly. I hope it's helpful to your need.

You can grab our software system

which contains other rule sets like Langton's. It also has our design of minial self-replicating loops.

The initial configuration for Byl's loop:

 XX
XLOX
XL+X
 X*

The rule set:

..... -> .      ....O -> .      ....L -> O      ...+X -> .      ...OO -> .
...OX -> .      ...LO -> O      ...LL -> .      ...LX -> .      ...X. -> .
...X+ -> X      ...XL -> L      ..+LL -> .      ..*OX -> .      ..O+. -> .
..OOX -> .      ..OL. -> *      ..OLO -> .      ..OLX -> .      ..L.X -> .
..L+. -> .      ..L+X -> .      ..LOX -> .      ..X.+ -> .      ..X.* -> .
..X.O -> .      ..X.X -> .      ..X+X -> .      ..X*. -> .      ..X*X -> .
..XX. -> .      ..XX* -> .      ..XXX -> .      .+... -> .      .*... -> .
.*.*. -> .      .O..* -> X      .O..X -> X      .O.+. -> .      .O.O. -> .
.X..* -> *      +..XL -> L      +.*XL -> *      +.OXL -> L      ++X.X -> +
+*X.X -> .      +O*XL -> L      +OOXL -> L      +OX.X -> +      +OX*L -> L
+LX.X -> +      +XO+L -> L      +XXLO -> L      *.OL. -> X      *.XXL -> .
*+..X -> X      *+X.. -> X      *OX.X -> +      *L..X -> *      *X..X -> *
*X.++ -> X      *XLX+ -> X      *XX.X -> .      O.... -> .      O...O -> .
O...L -> L      O..LL -> .      O.OXL -> L      O.L+. -> O      O.LX+ -> +
OOOX+ -> +      OOLX+ -> +      OOX+. -> +      OLLX+ -> +      OXOL* -> O
OXL++ -> +      OXL*+ -> L      OXX+O -> +      OXX+L -> +      L..O. -> .
L..L. -> .      L..XO -> O      L..XL -> L      L.+XL -> L      L.OO. -> .
L.OXO -> O      L.LXO -> O      L.LXL -> L      L.XXL -> L      L++XL -> L
L+LXL -> L      L*OX. -> X      L*LXO -> *      LO+XL -> L      LOOXL -> L
LOLX* -> O      LOLXO -> O      LOXXO -> O      LL+XX -> L      LLLXO -> O
LX.*L -> L      LX++L -> L      LX*+O -> *      LXO+L -> L      LXO*O -> O
LXOLX -> O      LXL+O -> O      X.... -> .      X...+ -> X      X...L -> X
X...X -> X      X..++ -> X      X..*O -> *      X..OO -> X      X..OX -> X
X..L+ -> X      X..LL -> X      X..X+ -> X      X..XO -> X      X.O*. -> X
X.LX. -> X      X.XL. -> X      X++.X -> X      X+*.X -> X      X+X.+ -> X
X+X.X -> X      X*+X. -> X      X**.+ -> X      X*X.X -> *      XO..+ -> X
XO+.X -> X      XO*.X -> X      XOX.+ -> X      XOX.* -> *      XOX.X -> X
XL..* -> X      XL+.X -> X      XL*.. -> X      XL*.X -> X      XLX.+ -> X
XLX.X -> X      XX..+ -> X      XX..X -> .      XX.*L -> L      XXO** -> X
The reduced rule set (when wildcard position, represented by underscore, is allowed. It simply means "doesn't matter" for those positions):
....L -> O      ...LO -> O      ...X+ -> X      ...XL -> L      ..OL. -> *
.O..* -> X      .O..X -> X      .X..* -> *      +..__ -> L      +.*__ -> *
+*X._ -> .      +O__L -> L      +XO+_ -> L      +XX__ -> L      *.O__ -> X
*.XXL -> .      *+___ -> X      *OX__ -> +      *XX.X -> .      *X__+ -> X
O.... -> .      O...O -> .      O...L -> L      O..LL -> .      OO_+_ -> +
OXL*_ -> L      OX_+_ -> +      O__X+ -> +      L.._. -> .      L.OO_ -> .
L._XO -> O      L*OX. -> X      L*LXO -> *      LOL__ -> O      LOXX_ -> O
LLL__ -> O      LX*+_ -> *      LXO*O -> O      LXL+O -> O      X.... -> .
X..*O -> *      X*X._ -> *      XOX.* -> *      XX..X -> .      XX.*L -> L
_.OXL -> L
Expand this node
Expand/collapse
Expand this node
References
BL94
Michael Batty and Paul Longley. Fractal Cities. Academic Press, 1994. ISBN 0-12-455570-5.

DBG93
P Deadman, R. D Brown, and H. R Gimblett. Modelling rural residential settlement patterns with cellular automata. Journal of environmental management, 37(2):147, February 1993.

DS92
C. Dytham and B. Shorrocks. Selection, patches and genetic variation: a CA modelling drosophila populations. Evolutionary Ecology, 6:342-351, 1992.

EEK93
G. Bard Ermentrout and Leah Edelstein-Keshet. Cellular automata approaches to biological modeling. Journal of Theoretical Biology, 160:97-133, January 1993.

GNH85
D. G. Green, House A. P. N., and S. M. House. Simulating spatial patterns in forest ecosystems. Mathematics and Computers in Simulation, 27:191-198, 1985.

Gre82
D. G. Green. Simulated effects of fire, dispersal and spatial pattern on ceompetition within forest mosaics. Vegetation, 82:139-154, 1982.

Gre90
David Geoffrey Green. Cellular automata models of crown-of-thorns outbreaks. In R. H. Bradbury, editor, Acanthaster and the Coral Reef:A Theoretical Perspective, volume 88 of Lecture Notes in Biomathematics, pages 169-188. Springer-Verlag, Berlin, 1990.

Gua87
P. Guan. Cellular automaton public-key cryptosystems. Complex Systems, 1, 1987.

Gut92
Howard Gutowitz. Method and apparatus for encryption, decryption, and authentication using dynamical systems. U.S. Patent 5,365,589 Issued Nov. 15, 1994, 1992.

Gut93
Howard Gutowitz. Cryptography with dynamical systems. In N. Boccara, E. Goles, S. Martinez, and P. Picco, editors, Cellular Automata and Cooperative Phenomena, pages 237-274. Kluwer Academic Publishers, 1993.

HG93
B. A. Huberman and N. Glance. Evolutionary games and computer simulations. Proceedings of the National Academy of Sciences, USA, 90:7716-7718, August 1993.

HH90
P. Hogeweg and B. Hesper. Crowns crowding:an individual oriented model of the acanthaster phenomenon. In R. H. In Bradbury, editor, Acanthaster and the Coral Reef:A Theoretical Perspective, volume 88 of Lecture Notes in Biomathematics, pages 169-188. Springer-Verlag, Berlin, 1990.

Hog88
P. Hogeweg. Cellular automata as a paradigm for ecological modeling. applied Mathematics and Computation, 27:81-100, 1988.

Ita88
Robert Itami. Cellular worlds-models for dynamic conceptions of landscape. Landscape Architecture, pages 52-57, July 1988.

Kar92
J. Kari. Cryptosystems based on reversible cellular automata. preprint, April 1992.

MS91
W. Meier and O. Staffelbach. Analysis of pseudo random sequences generated by cellular automata. Proceedings of Eurocrypt '91, pages 186-199, 1991.

NM92
Martin A. Nowak and Robert M. May. Evolutionary games and spatial chaos. Nature, 359:826-829, 1992.

Sat89
Kazuhiro Satoh. Computer experiment on the complex behavior of a two-dimensional cellular automaton as a phenomenological mpdel for an ecosystem. Journal of the Physical Society of Japan, 58(10):3842-3856, 1989.

Sat90
Kazuhiro Satoh. Single and multiarmed spiral patterns in a cellular automaton model for an ecosystem. Journal of the Physical Society of Japan, 59(12):4204-4207, 1990.

SHJD92
Jonathan Silvertown, Senino Holtier, Jeff Johnson, and Pam Dale. Cellular automaton models of interspecific competition for space-the effect of pattern on process. Journal of Ecology, 80:527-534, 1992.

SOB92
K. Sugihara, A. Okabe, and B. Boots. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley, 1992.

unk82
unknown, editor. Physics of Computation and Computational models of Physics, volume 21:3-4, 6-7, and 12, 1982.

WE00
R. White and G. Engelen. Urban system dynamics and cellular automata: Fractal structures between order and chaos. unknown, 1900.

WEU00
R. White, G. Engelen, and I. Uljee. Cellular automata modelling of fractal urban land use patterns: Forcasting change for planning applications. unknown, 1900.

Wol84
Stephan Wolfram. Random sequence generation by cellular automata. Adv. Appl. Math, 7:123, 1984.

Wol85
Stephan Wolfram. Cryptography with cellular automata. Proceedings of Crypto '85, pages 429-432, 1985.