On Compatibility of Discrete Relations

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


An approach to compatibility analysis of systems of discrete relations is proposed. Unlike the Gröbner basis technique, the proposed scheme is not based on the polynomial ring structure. It uses more primitive set-theoretic and topological concepts and constructions. We illustrate the approach by application to some two-state cellular automata. In the two-state case the Gröbner basis method is also applicable, and we compare both approaches.


Cellular Automaton Simplicial Complex Local Rule Canonical Decomposition Sierpinski Gasket 
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.
    Toffoli, T.: Occam, Turing, von Neumann, Jaynes:  How much can you get for how little (A conceptual introduction to cellular automata). In: Automi Cellulari per la Ricerca e l’Industria, Rende (CS), Italy, September 29–30 (1994)Google Scholar
  2. 2.
    Hilton, P.J., Wylie, S.: Homology Theory: An Introduction to Algebraic Topology. Cambridge University Press, New York (1960)zbMATHCrossRefGoogle Scholar
  3. 3.
    Lidl, R., Niederreiter, H.: Finite Fields. Encyclopedia of Math. and its Appl, vol. 20. Cambridge University Press, London (1997)Google Scholar
  4. 4.
    ’t Hooft, G.: Dimensional Reduction in Quantum Gravity, Essay dedicated to Abdus Salam, Utrecht preprint THU-93/26, p. 13; id., arXiv: gr-qc/9310026Google Scholar
  5. 5.
    Bousso, R.: The Holographic Principle. Rev. Mod. Phys. 74, 825–874 (2002), arXiv: hep-th/0203101Google Scholar
  6. 6.
    Gardner, M.: On Cellular Automata Self-reproduction, the Garden of Eden and the Game of ‘Life’. Sci. Am. 224, 112–117 (1971)CrossRefGoogle Scholar
  7. 7.
    Wolfram, S.: A New Kind of Science. Wolfram Media, Inc., Champaign (2002)zbMATHGoogle Scholar
  8. 8.

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

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

Personalised recommendations