Skip to main content
SpringerLink
Log in

A complexity analysis of the elementary cellular automaton of rule 122

  • Notes
  • Published:
Chinese Science Bulletin

Abstract

S. Wolfram initiated the use of formal languages and automata theory in study of cellular automata (CAs). By means of extensive experiments with computer, he classified all CAs into four classes and conjectured that the limit languages of the third class of CAs, which produce chaotic aperiodic behavior, are not regular. Using symbolic dynamics and formal languages, we prove that the limit language of the elementary CA of rule 122 is neither regular nor context-free.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Wolfram, S., Cellular automata as models of complexity, Nature, 1984, 311(4): 419.

    Article  Google Scholar 

  2. Jackson, E. A., Perspective of Nonlinear Dynamics, Vol II, Cambridge: Cambridge Univ. Press, 1990.

    Google Scholar 

  3. Delorme, M., Mazoyer, J., Cellular Automata: A Parallel Model, Dordrecht/Boston/London: Kluwer Academic Publishers, 1999.

    Google Scholar 

  4. Wolfram, S., Theory and Application of Cellular Automata, Singapore: World Scientific, 1986.

    Google Scholar 

  5. Xie, H. M., Complexity and Dynamical Systems (in Chinese), Shanghai: Shanghai Scientific and Technological Education Publishing House, 1994.

    Google Scholar 

  6. Badii, R., Politi, A., Complexity: Hierarchical Structures and Scaling in Physics, Cambridge: Cambridge Univ. Press, 1997.

    Google Scholar 

  7. Worlfram, S., Computation theory of cellular automata, Comm. Math. Phys. 1984(96): 15.

  8. Hurd, L. P., Recursive cellular automata invariant sets, Complex System, 1990(4): 119.

  9. Hurd, L. P., Nonrecursive cellular automata invariant sets, Complex System, 1990(4): 131.

  10. Hopcroft, J. E., Ullman, J. D., Introduction to Automata Theory Languages and Computation, Reading MA: Addison-Wesley, 1979.

    Google Scholar 

  11. Xie, H. M., Grammatical Complexity and One-dimensional Dynamical System, Singapore: World Scientific, 1996.

    Google Scholar 

  12. Ogden, W., A helpful result for proving inherent ambiguity, Math. Systems Theory, 1968, 2: 191.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mathematics Department, Suzhou University, 215006, Suzhou, China

    Zhisong Jiang

Authors
  1. Zhisong Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhisong Jiang.

About this article

Cite this article

Jiang, Z. A complexity analysis of the elementary cellular automaton of rule 122. Chin.Sci.Bull. 46, 600–603 (2001). https://doi.org/10.1007/BF02900420

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02900420

Keywords

Search

Navigation