SpringerLink
Log in

Asynchronous cellular automata and dynamical properties

  • Published:
Natural Computing Aims and scope Submit manuscript

Abstract

In this article the dynamical behaviour of asynchronous cellular automata (CA) is formally studied. Classical CA properties as surjectivity, injectivity, sensitivity, expansivity, transitivity, dense periodic orbits and equicontinuity have been adapted to the asynchronous case. We also deal with stability of properties with respect to perturbations on some update sequences which produce a significant dynamical behaviour.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Acerbi L, Dennunzio A, Formenti E (2007) Shifting and lifting of cellular automata. In: CiE, LNCS, vol 4497. Springer, Berlin, pp 1–10

  • Acerbi L, Dennunzio A, Formenti E (2009) Conservation of some dynamical properties for operations on cellular automata. Theor Comput Sci 410:3685–3693

    Article  MathSciNet  MATH  Google Scholar 

  • Amar P, Bernot G, Norris V (2004) Hsim: a simulation programme to study large assemblies of proteins. J Biol Phys Chem 4:79–84

    Article  Google Scholar 

  • Bersini H, Detours V (1994) Asynchrony induces stability in cellular automata based models. In: Proc. of artificial life IV. MIT Press, Cambridge, pp 382–387

  • Buvel R, Ingerson T (1984) Structure in asynchronous cellular automata. Physica D 1:59–68

    MathSciNet  Google Scholar 

  • Cattaneo G, Dennunzio A, Margara L (2002) Chaotic subshifts and related languages applications to one-dimensional cellular automata. Fundam Inf 52:39–80

    MathSciNet  MATH  Google Scholar 

  • Cattaneo G, Dennunzio A, Margara L (2004) Solution of some conjectures about topological properties of linear cellular automata. Theor Comput Sci 325(2):249–271

    Article  MathSciNet  MATH  Google Scholar 

  • Cattaneo G, Dennunzio A, Formenti E, Provillard J (2009) Non-uniform cellular automata. In: LATA, LNCS, vol 5457. Springer, Berlin, pp 302–313

  • Chaudhuri P, Chowdhury D, Nandi S, Chattopadhyay S (1997) Additive cellular automata theory and applications, vol 1. IEEE Press, New York

    MATH  Google Scholar 

  • Chopard B (2010) Modelling physical systems by cellular automata. In: Rozenberg G et al (eds) Handbook of natural computing: theory, experiments, and applications. Springer, Heidelberg

    Google Scholar 

  • Dennunzio A, Formenti E (2008) Decidable properties of 2d cellular automata. In: Developments in language theory. LNCS, vol 5257. Springer, Berlin, pp 264–275

  • Dennunzio A, Di Lena P, Formenti E, Margara L (2009) On the directional dynamics of additive cellular automata. Theor Comput Sci 410:4823–4833

    Article  MathSciNet  MATH  Google Scholar 

  • Dennunzio A, Masson B, Guillon P (2009) Sand automata as cellular automata. Theor Comput Sci 410:3962–3974

    Article  MathSciNet  MATH  Google Scholar 

  • Dennunzio A, Formenti E, Kůrka P (2010) Cellular automata dynamical systems. In: Rozenberg G et al (eds) Handbook of natural computing: theory, experiments, and applications. Springer, Heidelberg

    Google Scholar 

  • Farina F, Dennunzio A (2008) A predator–prey cellular automaton with parasitic interactions and environmental effects. Fundam Inf 83:337–353

    MathSciNet  MATH  Google Scholar 

  • Fatès N, Morvan M (2005) An experimental study of robustness to asynchronism for elementary cellular automata. Complex Syst 16(1):1–27

    Google Scholar 

  • Fatès N, Morvan M, Schabanel N, Thierry E (2006a) Fully asynchronous behaviour of double-quiescent elementary cellular automata. Theor Comput Sci 362:1–16

    Article  MATH  Google Scholar 

  • Fatès N, Regnault D, Schabanel N, Thierry E (2006b) Asynchronous behaviour of double-quiescent elementary cellular automata. In: Proceedings of LATIN2006, LNCS, vol 3887. Springer, Berlin, pp 455–466

  • Fukś H (2002) Non-deterministic density classification with diffusive probabilistic cellular automata. Phys Rev E 66(2):066106

    Google Scholar 

  • Kůrka P (1997) Languages, equicontinuity and attractors in cellular automata. Ergod Theory Dyn Syst 17:417–433

    Article  MATH  Google Scholar 

  • Kůrka P (2009) Topological dynamics of one-dimensional cellular automata. In: Meyers B (ed) Mathematical basis of cellular automata, encyclopedia of complexity and system science. Springer, Berlin, pp 2232–2242

    Google Scholar 

  • Levenshtein V (1966) Binary codes capable of correcting deletions, insertions, and reversals. Sov Phys Dokl 10(8):707–710

    MathSciNet  Google Scholar 

  • Maruoka A, Kimura M (1979) Injectivity and surjectivity for parallel maps for CA. J Comput Syst Sci 18:47–64

    Article  MathSciNet  MATH  Google Scholar 

  • Nakamura K (1974) Asynchronous cellular automata and their computational ability. Syst Comput Control 5:58–66

    Google Scholar 

  • Regnault D (2006) Abrupt behaviour changes in cellular automata under asynchronous dynamics. In: Electronic proc. of 2nd European conference on complex systems, ECCS, Oxford

  • Regnault D, Schabanel N, Thierry E (2009) Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority. Theor Comput Sci 410:4844–4855

    Article  MathSciNet  MATH  Google Scholar 

  • Schönfisch B, de Roos A (1999) Synchronous and asynchronous updating in cellular automata. BioSystems 51:123–143

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336, 20126, Milano, MI, Italy

    Luca Manzoni

Authors
  1. Luca Manzoni
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luca Manzoni.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Manzoni, L. Asynchronous cellular automata and dynamical properties. Nat Comput 11, 269–276 (2012). https://doi.org/10.1007/s11047-012-9308-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11047-012-9308-y

Keywords

Search

Navigation