[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Complexity of Linear Cellular Automata over ℤ m

  • Conference paper
Advances in Natural Computation (ICNC 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3610))

Included in the following conference series:

  • 1983 Accesses

Abstract

Cellular automata(CA) is not only a discrete dynamical system with infinite dimensions, but also an important computational model. How simple can a CA be and yet support interesting and complicated behavior. There are many unsolved problems in the theory of CA, which appeal many researchers to focus their attentions on the field, especially subclass of CA – linear CA. These studies cover the topological properties, chaotical properties, invertibility, attractors and the classification of linear CA etc.. This is a survey of known results and open questions of D-dimensional linear CA over ℤ m .

Supported by Natural Science Foundation of China (NSFC) grant 60103015 and The Project-sponsored by SRF for ROCS, SEM.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Cattaneo, G., Formenti, E., Manzini, G., Margara, L.: Erogdicity, transitivity, and regularity for additive cellular automata over \({\mathbb Z}_m\). Theoret. Comput. Sci. 233, 147–164 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  2. Codenotti, B., Margara, L.: Transitive cellular automata are sensitive. Amer. Math. Monthly 103, 58–62 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  3. Čulik, K., Yu, S.: Undecidability of CA classification achemes. Complex Systems 2, 177–190 (1988)

    MATH  MathSciNet  Google Scholar 

  4. D’amico, M., Manzini, G., Margara, L.: On computinmg the entropy of cellular automata. Lecture Notes in Mathematica, vol. 1443, pp. 470–481 (1998)

    Google Scholar 

  5. Devaney, R.L.: An introduction to chaotic dynamical systems, 2nd edn. Addison-Wesley, Reading (1989)

    MATH  Google Scholar 

  6. Favati, P., Lotti, G., Margara, L.: Additive one dimensional cellular automata are chaotic according to Devaney’s definition of chaos. Theoret. Comput. Sci. 174(1-2), 157–170 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  7. Finelli, M., Manzini, G., Margara, L.: Lyapunov exponents vs expansivity and sensitivity in cellular automata. J. Complexity 14, 210–233 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  8. Hurd, L., Kari, J., Čulik, K.: The topological entropy of cellular automata is uncomputable. Ergodic Theory and Dynamical Systems 12, 255–265 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  9. Hurley, M.: Attractor in cellular automata. Ergodic Theory and Dynamical Systems 10, 131–140 (1990)

    MATH  MathSciNet  Google Scholar 

  10. Ito, M., Osato, N., Nasu, M.: Linear cellular automata over \({\mathbb Z}_m\). J. Comput. System Sci. 27, 125–140 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  11. Kari, J.: Reversibility of 2D cellular automata is undecidable. Physica D 45, 379–385 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  12. Kurka, P.: Languages, equicontinuity and attractors in cellular automata. Ergodic Theory and Dynamical Systems 17, 417–433 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  13. Kundsen, C.: Chaos without nonperiodicity. Amer. Math. Monthly 101, 563–565 (1994)

    Article  MathSciNet  Google Scholar 

  14. Manzini, G.: Characterization of sensitive linear cellular automata with respect to the counting distance. In: Brim, L., Gruska, J., Zlatuška, J. (eds.) MFCS 1998. LNCS, vol. 1450, pp. 825–833. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  15. Manzini, G., Magara, L.: A complete and effciently computable topologyical calssification of D-dimensional linear cellula automata over \({\mathbb Z}_m\). Theoret. Comput. Sci. 221, 157–177 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  16. Manzini, G., Margara, L.: Attractor of linear cellular automata. J. Comput. system Sci. 58, 597–610 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  17. Sato, T.: Group Structured linear cellular automata over \({\mathbb Z}_m\). J. Comput. System Sci. 27, 18–23 (1999)

    Google Scholar 

  18. Sato, T.: Erogodicity of linear cellular automata over \({\mathbb Z}_m\). Inform. process. lett. 61(3), 169–172 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  19. Sutner, K.: A note on Čulik-Yu classes. Complex Syst. 3, 107 (1989)

    MATH  MathSciNet  Google Scholar 

  20. Wolfram, S.: Universility and complexity in cellular automata. Physica D 10, 1–35 (1984)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. AI Institute, College of Computer Science, Zhejiang university, Hangzhou, 310027, China

    Xiaogang Jin

  2. College of Software, Zhejiang University of Technology, Hangzhou, 310032, China

    Weihong Wang

Authors
  1. Xiaogang Jin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Weihong Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Electrical and Electronic Engineering, Nanyang Technological University, Block S1, Nanyang Avenue, 639798, Singapore

    Lipo Wang

  2. School of Software, Sun Yat-Sen University, 510275, Guangzhou, China

    Ke Chen

  3. School of Computer Engineering, Nanyang Technological University, BLK N4, 2b-39, Nanyang Avenue, 639798, Singapore

    Yew Soon Ong

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Jin, X., Wang, W. (2005). Complexity of Linear Cellular Automata over ℤ m . In: Wang, L., Chen, K., Ong, Y.S. (eds) Advances in Natural Computation. ICNC 2005. Lecture Notes in Computer Science, vol 3610. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11539087_160

Download citation

  • DOI: https://doi.org/10.1007/11539087_160

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-28323-2

  • Online ISBN: 978-3-540-31853-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation