Skip to main content
SpringerLink
Log in
Book cover

Encyclopedia of Complexity and Systems Science pp 1–21Cite as

Asynchronous Cellular Automata

Glossary

Configurations:

These objects represent the global state of the cellular automaton under study. The set of configurations is denoted by Q ℒ, where Q is the set of states of the cells and ℒ is the space of cells. In this text, we mainly consider finite configurations with periodic boundary conditions. In one dimension, we use ℒ = ℤ/nℤ, the class of equivalence of integers modulo n.

Convergence:

When started from a given initial condition, the system evolves until it attains a set of configurations from which it will not escape. It is a difficult problem to know in general what are the properties of these attractive sets and how long it takes for the system to attain them. In this text, we are particularly interested in the case where these sets are limited to a single configuration, that is, when the system converges to a fixed point. Fixed points play a special role in the theory of asynchronous cellular automata because synchronous and (classical) asynchronous models have the...

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

Bibliography

  • Belgacem S, Fatès N (2012) Robustness of multi-agent models: the example of collaboration between turmites with synchronous and asynchronous updating. Complex Syst 21(3):165–182

    MathSciNet  MATH  Google Scholar 

  • Blok HJ, Bergersen B (1999) Synchronous versus asynchronous updating in the “game of life”. Phys Rev E 59:3876–3879

    Article  ADS  Google Scholar 

  • Bolt W, Wolnik B, Baetens JM, De Baets B (2016) On the identification of α-asynchronous cellular automata in the case of partial observations with spatially separated gaps. In: De Tré G, Grzegorzewski P, Kacprzyk J, Owsinski JW, Penczek W, Zadrozny S (eds) Challenging problems and solutions in intelligent systems. Springer, pp 23–36

    Google Scholar 

  • Bouré O, Fatès N, Chevrier V (2012) Probing robustness of cellular automata through variations of asynchronous updating. Nat Comput 11:553–564

    Article  MathSciNet  MATH  Google Scholar 

  • Bouré O, Fatès N, Chevrier V (2013a) First steps on asynchronous lattice-gas models with an application to a swarming rule. Nat Comput 12(4):551–560

    Article  MathSciNet  MATH  Google Scholar 

  • Bouré O, Fatès N, Chevrier V (2013b) A robustness approach to study metastable behaviours in a lattice-gas model of swarming. In: Kari J, Kutrib M, Malcher A (eds) Proceedings of automata’13, volume 8155 of lecture notes in computer science. Springer, pp 84–97

    Google Scholar 

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

    MathSciNet  Google Scholar 

  • Chassaing P, Gerin L (2007) Asynchronous cellular automata and brownian motion. In: DMTCS proceedings of AofA’07, volume AH, pp 385–402

    Google Scholar 

  • Chevrier V, Fatès N (2010) How important are updating schemes in multi-agent systems? An illustration on a multi-turmite model. In: Proceedings of AAMAS ‘10. International Foundation for Autonomous Agents and Multiagent Systems, Richland, pp 533–540

    Google Scholar 

  • Cornforth D, Green DG, Newth D (2005) Ordered asynchronous processes in multi-agent systems. Physica D 204(1–2):70–82

    Article  ADS  MathSciNet  Google Scholar 

  • de Mas JF (2017) Coalescence in fully asynchronous elementary cellular automata. Technical report, HAL preprint hal-01627454

    Google Scholar 

  • de Oliveira PPB (2014) On density determination with cellular automata: results, constructions and directions. J Cell Autom 9(5–6):357–385

    MathSciNet  MATH  Google Scholar 

  • Dennunzio A, Formenti E, Manzoni L (2012) Computing issues of asynchronous CA. Fundamenta Informaticae 120(2):165–180

    MathSciNet  MATH  Google Scholar 

  • Dennunzio A, Formenti E, Manzoni L, Mauri G (2013) m-asynchronous cellular automata: from fairness to quasi-fairness. Nat Comput 12(4):561–572

    Article  MathSciNet  MATH  Google Scholar 

  • Dennunzio A, Formenti E, Manzoni L, Mauri G, Porreca AE (2017) Computational complexity of finite asynchronous cellular automata. Theor Comput Sci 664:131–143

    Article  MathSciNet  MATH  Google Scholar 

  • Fatès N (2009) Asynchronism induces second order phase transitions in elementary cellular automata. J Cell Autom 4(1):21–38

    MathSciNet  MATH  Google Scholar 

  • Fatès N (2010) Does life resist asynchrony? In: Adamatzky A (ed) Game of life cellular automata. Springer, London, pp 257–274

    Chapter  Google Scholar 

  • Fatès N (2013a) A note on the classification of the most simple asynchronous cellular automata. In: Kari J, Kutrib M, Malcher A (eds) Proceedings of automata’13, volume 8155 of lecture notes in computer science. Springer, pp 31–45

    Google Scholar 

  • Fatès N (2013b) Stochastic cellular automata solutions to the density classification problem – when randomness helps computing. Theory Comput Syst 53(2):223–242

    Article  MathSciNet  MATH  Google Scholar 

  • Fatès N (2014a) A guided tour of asynchronous cellular automata. J Cell Autom 9(5–6):387–416

    MathSciNet  MATH  Google Scholar 

  • Fatès N (2014b) Quick convergence to a fixed point: a note on asynchronous elementary cellular automata. In: Was J, Sirakoulis GC, Bandini S (eds) Proceedings of ACRI’14, volume 8751 of lecture notes in computer science. Springer, pp 586–595

    Google Scholar 

  • Fatès N, Gerin L (2009) Examples of fast and slow convergence of 2D asynchronous cellular systems. Old City Publishing. J Cell Autom 4(4):323–337. http://www.oldcitypublishing.com/journals/jca-home/

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

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Fatès N, Regnault D, Schabanel N, Thierry E (2006b) Asynchronous behavior of double-quiescent elementary cellular automata. In: Correa JR, Hevia A, Kiwi MA (eds) Proceedings of LATIN 2006, volume 3887 of lecture notes in computer science. Springer, pp 455–466

    Google Scholar 

  • Fatès N, Sethi B, Das S (2017) On the reversibility of ecas with fully asynchronous updating: the recurrence point of view. To appear in a monography edited by Andrew Adamatzky – Preprint available on the HAL server, id: hal-01571847

    Google Scholar 

  • Fukś H (2002) Nondeterministic density classification with diffusive probabilistic cellular automata. Phys Rev E 66(6):066106

    Article  ADS  Google Scholar 

  • Fukś H, Fatès N (2015) Local structure approximation as a predictor of second-order phase transitions in asynchronous cellular automata. Nat Comput 14(4):507–522

    Article  MathSciNet  Google Scholar 

  • Gács P (2001) Deterministic computations whose history is independent of the order of asynchronous updating. Technical report – arXiv:cs/0101026

    Google Scholar 

  • Gerin L (2017) Epidemic automaton and the eden model: various aspects of robustness. Text to appear in a monography on probabilistic cellular automata. Springer

    Google Scholar 

  • Huberman BA, Glance N (1993) Evolutionary games and computer simulations. Proc Natl Acad Sci U S A 90:7716–7718

    Article  ADS  MATH  Google Scholar 

  • Kari J, Taati S (2015) Statistical mechanics of surjective cellular automata. J Stat Phys 160(5):1198–1243

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • Lee J, Peper F (2008) On brownian cellular automata. In: Adamatzky A, Alonso-Sanz R, Lawniczak AT, Martínez GJ, Morita K, Worsch T (eds) Proceedings of automata 2008. Luniver Press, Frome, pp 278–291

    Google Scholar 

  • Lee J, Adachi S, Peper F, Morita K (2004) Asynchronous game of life. Phys D 194(3–4):369–384

    Article  MathSciNet  MATH  Google Scholar 

  • Lee J, Peper F, Cotofana SD, Naruse M, Ohtsu M, Kawazoe T, Takahashi Y, Shimokawa T, Kish LB, Kubota T (2016a) Brownian circuits: designs. Int J Unconv Comput 12(5–6):341–362

    Google Scholar 

  • Lee J, Peper F, Leibnitz K, Ping G (2016b) Characterization of random fluctuation-based computation in cellular automata. Inf Sci 352–353:150–166

    Article  Google Scholar 

  • Louis P-Y (2015) Supercritical probabilistic cellular automata: how effective is the synchronous updating? Nat Comput 14(4):523–534

    Article  MathSciNet  Google Scholar 

  • Macauley M, Mortveit HS (2010) Coxeter groups and asynchronous cellular automata. In: Bandini S, Manzoni S, Umeo H, Vizzari G (eds) Proceedings of ACRI’10, volume 6350 of lecture notes in computer science. Springer, pp 409–418

    Google Scholar 

  • Macauley M, Mortveit HS (2013) An atlas of limit set dynamics for asynchronous elementary cellular automata. Theor Comput Sci 504:26–37. Discrete mathematical structures: from dynamics to complexity

    Article  MathSciNet  MATH  Google Scholar 

  • Macauley M, McCammond J, Mortveit HS (2008) Order independence in asynchronous cellular automata. J Cell Autom 3(1):37–56

    MathSciNet  MATH  Google Scholar 

  • Mairesse J, Marcovici I (2014) Around probabilistic cellular automata. Theor Comput Sci 559:42–72. Non-uniform cellular automata

    Article  MathSciNet  MATH  Google Scholar 

  • Moore EF (1962) Machine models of self-reproduction. Proc Symp Appl Math 14:17–33. (Reprinted in Essays on cellular automata, Burks AW (ed), University of Illinois Press, 1970)

    Article  MATH  Google Scholar 

  • Morita K (2008) Reversible computing and cellular automata – a survey. Theor Comput Sci 395(1):101–131

    Article  MathSciNet  MATH  Google Scholar 

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

    MathSciNet  Google Scholar 

  • Nakamura K (1981) Synchronous to asynchronous transformation of polyautomata. J Comput Syst Sci 23(1):22–37

    Article  MathSciNet  MATH  Google Scholar 

  • Nowak MA, May RM (1992) Evolutionary games and spatial chaos. Nature 359:826–829

    Article  ADS  Google Scholar 

  • Peper F, Lee J, Adachi S, Mashiko S (2003) Laying out circuits on asynchronous cellular arrays: a step towards feasible nanocomputers? Nanotechnology 14(4):469

    Article  ADS  Google Scholar 

  • Peper F, Lee J, Isokawa T (2010) Brownian cellular automata. J Cell Autom 5(3):185–206

    MathSciNet  MATH  Google Scholar 

  • Ramos AD, Leite A (2017) Convergence time and phase transition in a non-monotonic family of probabilistic cellular automata. J Stat Phys 168(3):573–594

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • Regnault D (2013) Proof of a phase transition in probabilistic cellular automata. In: Béal MP and Carton O (eds) Proceedings of developments in language theory, volume 7907 of lecture notes in computer science. Springer, pp 433–444

    Google Scholar 

  • 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(47–49):4844–4855

    Article  MathSciNet  MATH  Google Scholar 

  • Regnault D, Schabanel N, Thierry E (2010) On the analysis of “simple” 2d stochastic cellular automata. Discrete Math Theor Comput Sci 12(2):263–294

    MathSciNet  MATH  Google Scholar 

  • Rouquier J-B, Morvan M (2009) Coalescing cellular automata: synchronization by common random source for asynchronous updating. J Cell Autom 4(1):55–78

    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 

  • Sethi B, Fatès N, Das S (2014) Reversibility of elementary cellular automata under fully asynchronous update. In: Gopal TV, Agrawal M, Li A, Cooper B (eds) Proceedings of TAMC’14, volume 8402 of lecture notes in computer science. Springer, pp 39–49

    Google Scholar 

  • Sethi B, Roy S, Das S (2016) Asynchronous cellular automata and pattern classification. Complexity 21:370–386

    Article  ADS  MathSciNet  Google Scholar 

  • Silva F, Correia L (2013) An experimental study of noise and asynchrony in elementary cellular automata with sampling compensation. Nat Comput 12(4):573–588

    Article  MathSciNet  Google Scholar 

  • Silva F, Correia L, Christensen AL (2015) Modelling synchronisation in multirobot systems with cellular automata: analysis of update methods and topology perturbations. In: Sirakoulis GC, Adamatzky A (eds) Robots and lattice automata, volume 13 of emergence, complexity and computation. Springer International Publishing, Springer. pp 267–293

    Google Scholar 

  • Takada Y, Isokawa T, Peper F, Matsui N (2007a) Asynchronous self-reproducing loops with arbitration capability. Phys D Nonlinear Phenom 227(1):26–35

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • Takada Y, Isokawa T, Peper F, Matsui N (2007b) Asynchronous self-reproducing loops with arbitration capability. Phys D 227(1):26–35

    Article  MathSciNet  MATH  Google Scholar 

  • Vichniac GY (1984) Simulating physics with cellular automata. Phys D Nonlinear Phenom 10(1):96–116

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • Vielhaber M (2013) Computation of functions on n bits by asynchronous clocking of cellular automata. Nat Comput 12(3):307–322

    Article  MathSciNet  MATH  Google Scholar 

  • Wacker S, Worsch T (2013) On completeness and decidability of phase space invertible asynchronous cellular automata. Fundam Informaticae 126(2–3):157–181

    MathSciNet  MATH  Google Scholar 

  • Wolfram S (1985) Twenty problems in the theory of cellular automata. Phys Scr T9:170

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • Worsch T (2013) Towards intrinsically universal asynchronous CA. Nat Comput 12(4):539–550

    Article  MathSciNet  MATH  Google Scholar 

  • Yamashita T, Isokawa T, Peper F, Kawamata I, Hagiya M (2017) Turing-completeness of asynchronous non-camouflage cellular automata. In: Dennunzio A, Formenti E, Manzoni L, Porreca AE (eds) Proceedings of AUTOMATA 2017, volume 10248 of lecture notes in computer science. Springer, pp 187–199

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LORIA UMR 7503, Inria Nancy – Grand Est, Nancy, France

    Nazim Fatès

Authors
  1. Nazim Fatès
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nazim Fatès .

Editor information

Editors and Affiliations

  1. Ramtech Ltd., Larkspur, California, USA

    Robert A. Meyers

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Science+Business Media LLC

About this entry

Check for updates. Verify currency and authenticity via CrossMark

Cite this entry

Fatès, N. (2018). Asynchronous Cellular Automata. In: Meyers, R. (eds) Encyclopedia of Complexity and Systems Science. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27737-5_671-1

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-27737-5_671-1

  • Received:

  • Accepted:

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-27737-5

  • Online ISBN: 978-3-642-27737-5

  • eBook Packages: Springer Reference Physics and AstronomyReference Module Physical and Materials ScienceReference Module Chemistry, Materials and Physics

Publish with us

Policies and ethics

Chapter history

  1. Latest

    Asynchronous Cellular Automata
    Published:
    21 February 2018

    DOI: https://doi.org/10.1007/978-3-642-27737-5_671-2

  2. Original

    Asynchronous Cellular Automata
    Published:
    23 January 2018

    DOI: https://doi.org/10.1007/978-3-642-27737-5_671-1

Search

Navigation