Cellular Automata with Symmetric Local Rules

  • Vladimir V. Kornyak
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4194)


The cellular automata with local permutation invariance are considered. We show that in the two-state case the set of such automata coincides with the generalized Game of Life family. We count the number of equivalence classes of the rules under consideration with respect to permutations of states. This reduced number of rules can be efficiently generated in many practical cases by our C program. Since a cellular automaton is a combination of a local rule and a lattice, we consider also maximally symmetric two-dimensional lattices. In addition, we present the results of compatibility analysis of several rules from the Life family.


Cellular Automaton Life Family Local Rule Regular Lattice Klein Bottle 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Wolfram, S.: A New Kind of Science. Wolfram Media, Inc. (2002)Google Scholar
  2. 2.
    Gardner, M.: On cellular automata self-reproduction, the garden of Eden and the game of life. Sci. Am. 224, 112–117 (1971)CrossRefGoogle Scholar
  3. 3.
  4. 4.
    Harary, F.: Graph Theory. Addison-Wesley Publishing Company, Reading (1969)Google Scholar
  5. 5.
    Grunbaum, B., Sheppard, G.C.: Tilings and Patterns. W. H. Freeman, New York (1987)Google Scholar
  6. 6.
    Atiyah, M.F., Sutcliffe, P.M.: Polyhedra in Physics, Chemistry and Geometry. Milan Journal of Mathematics 71, 33–58 (2003), zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Kornyak, V.V.: On Compatibility of discrete relations. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2005. LNCS, vol. 3718, pp. 272–284. Springer, Heidelberg (2005), CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Vladimir V. Kornyak
    • 1
  1. 1.Laboratory of Information TechnologiesJoint Institute for Nuclear ResearchDubnaRussia

Personalised recommendations