Encyclopedia of Complexity and Systems Science

Living Edition
| Editors: Robert A. Meyers

Asynchronous Cellular Automata

  • Nazim FatèsEmail author
Living reference work entry

Latest version View entry history

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

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 to check access.

Bibliography

  1. 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–182MathSciNetzbMATHGoogle Scholar
  2. Blok HJ, Bergersen B (1999) Synchronous versus asynchronous updating in the “game of life”. Phys Rev E 59:3876–3879ADSCrossRefGoogle Scholar
  3. 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–36Google Scholar
  4. Bouré O, Fatès N, Chevrier V (2012) Probing robustness of cellular automata through variations of asynchronous updating. Nat Comput 11:553–564MathSciNetCrossRefzbMATHGoogle Scholar
  5. 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–560MathSciNetCrossRefzbMATHGoogle Scholar
  6. 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, Gießen, Germany, pp 84–97Google Scholar
  7. Buvel RL, Ingerson TE (1984) Structure in asynchronous cellular automata. Physica D 1:59–68MathSciNetGoogle Scholar
  8. Chassaing P, Gerin L (2007) Asynchronous cellular automata and brownian motion. In: DMTCS proceedings of AofA’07, volume AH. Juan les Pins, France, pp 385–402Google Scholar
  9. 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–540Google Scholar
  10. Cornforth D, Green DG, Newth D (2005) Ordered asynchronous processes in multi-agent systems. Physica D 204(1–2):70–82ADSMathSciNetCrossRefGoogle Scholar
  11. de Mas JF (2017) Coalescence in fully asynchronous elementary cellular automata. Technical report, HAL preprint hal-01627454Google Scholar
  12. de Oliveira PPB (2014) On density determination with cellular automata: results, constructions and directions. J Cell Autom 9(5–6):357–385MathSciNetzbMATHGoogle Scholar
  13. Dennunzio A, Formenti E, Manzoni L (2012) Computing issues of asynchronous CA. Fundamenta Informaticae 120(2):165–180MathSciNetzbMATHGoogle Scholar
  14. Dennunzio A, Formenti E, Manzoni L, Mauri G (2013) m-asynchronous cellular automata: from fairness to quasi-fairness. Nat Comput 12(4):561–572MathSciNetCrossRefzbMATHGoogle Scholar
  15. Dennunzio A, Formenti E, Manzoni L, Mauri G, Porreca AE (2017) Computational complexity of finite asynchronous cellular automata. Theor Comput Sci 664:131–143MathSciNetCrossRefzbMATHGoogle Scholar
  16. Fatès N (2009) Asynchronism induces second order phase transitions in elementary cellular automata. J Cell Autom 4(1):21–38MathSciNetzbMATHGoogle Scholar
  17. Fatès N (2010) Does life resist asynchrony? In: Adamatzky A (ed) Game of life cellular automata. Springer, London, pp 257–274CrossRefGoogle Scholar
  18. 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, Netherlands, pp 31–45.  https://doi.org/10.1007/s11047-013-9389-2
  19. Fatès N (2013b) Stochastic cellular automata solutions to the density classification problem – when randomness helps computing. Theory Comput Syst 53(2):223–242MathSciNetCrossRefzbMATHGoogle Scholar
  20. Fatès N (2014a) A guided tour of asynchronous cellular automata. J Cell Autom 9(5–6):387–416MathSciNetzbMATHGoogle Scholar
  21. 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. Krakow, Poland, Springer, pp 586–595Google Scholar
  22. 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/
  23. Fatès N, Morvan M (2005) An experimental study of robustness to asynchronism for elementary cellular automata. Complex Syst 16:1–27MathSciNetzbMATHGoogle Scholar
  24. Fatès N, Morvan M, Schabanel N, Thierry E (2006a) Fully asynchronous behavior of double-quiescent elementary cellular automata. Theor Comput Sci 362:1–16MathSciNetCrossRefzbMATHGoogle Scholar
  25. 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. Valdivia, Chile, Springer, pp 455–466Google Scholar
  26. 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-01571847Google Scholar
  27. Fukś H (2002) Nondeterministic density classification with diffusive probabilistic cellular automata. Phys Rev E 66(6):066106ADSCrossRefGoogle Scholar
  28. 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–522MathSciNetCrossRefGoogle Scholar
  29. Gács P (2001) Deterministic computations whose history is independent of the order of asynchronous updating. Technical report – arXiv:cs/0101026Google Scholar
  30. Gerin L (2017) Epidemic automaton and the eden model: various aspects of robustness. Text to appear in a monography on probabilistic cellular automata. SpringerGoogle Scholar
  31. Huberman BA, Glance N (1993) Evolutionary games and computer simulations. Proc Natl Acad Sci U S A 90:7716–7718ADSCrossRefzbMATHGoogle Scholar
  32. Kari J, Taati S (2015) Statistical mechanics of surjective cellular automata. J Stat Phys 160(5):1198–1243ADSMathSciNetCrossRefzbMATHGoogle Scholar
  33. 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–291Google Scholar
  34. Lee J, Adachi S, Peper F, Morita K (2004) Asynchronous game of life. Phys D 194(3–4):369–384MathSciNetCrossRefzbMATHGoogle Scholar
  35. 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–362Google Scholar
  36. Lee J, Peper F, Leibnitz K, Ping G (2016b) Characterization of random fluctuation-based computation in cellular automata. Inf Sci 352–353:150–166CrossRefGoogle Scholar
  37. Louis P-Y (2015) Supercritical probabilistic cellular automata: how effective is the synchronous updating? Nat Comput 14(4):523–534MathSciNetCrossRefGoogle Scholar
  38. 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, Ascoli Piceno, Italy, pp 409–418Google Scholar
  39. 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 complexityMathSciNetCrossRefzbMATHGoogle Scholar
  40. Macauley M, McCammond J, Mortveit HS (2008) Order independence in asynchronous cellular automata. J Cell Autom 3(1):37–56MathSciNetzbMATHGoogle Scholar
  41. Mairesse J, Marcovici I (2014) Around probabilistic cellular automata. Theor Comput Sci 559:42–72. Non-uniform cellular automataMathSciNetCrossRefzbMATHGoogle Scholar
  42. 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)CrossRefzbMATHGoogle Scholar
  43. Morita K (2008) Reversible computing and cellular automata – a survey. Theor Comput Sci 395(1):101–131MathSciNetCrossRefzbMATHGoogle Scholar
  44. Nakamura K (1974) Asynchronous cellular automata and their computational ability. Syst Comput Controls 5(5):58–66MathSciNetGoogle Scholar
  45. Nakamura K (1981) Synchronous to asynchronous transformation of polyautomata. J Comput Syst Sci 23(1):22–37MathSciNetCrossRefzbMATHGoogle Scholar
  46. Nowak MA, May RM (1992) Evolutionary games and spatial chaos. Nature 359:826–829ADSCrossRefGoogle Scholar
  47. Peper F, Lee J, Adachi S, Mashiko S (2003) Laying out circuits on asynchronous cellular arrays: a step towards feasible nanocomputers? Nanotechnology 14(4):469ADSCrossRefGoogle Scholar
  48. Peper F, Lee J, Isokawa T (2010) Brownian cellular automata. J Cell Autom 5(3):185–206MathSciNetzbMATHGoogle Scholar
  49. 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–594ADSMathSciNetCrossRefzbMATHGoogle Scholar
  50. 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, Marne-la-Vallée, France, pp 433–444Google Scholar
  51. 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–4855MathSciNetCrossRefzbMATHGoogle Scholar
  52. Regnault D, Schabanel N, Thierry E (2010) On the analysis of “simple” 2d stochastic cellular automata. Discrete Math Theor Comput Sci 12(2):263–294MathSciNetzbMATHGoogle Scholar
  53. Rouquier J-B, Morvan M (2009) Coalescing cellular automata: synchronization by common random source for asynchronous updating. J Cell Autom 4(1):55–78MathSciNetzbMATHGoogle Scholar
  54. Schönfisch B, de Roos A (1999) Synchronous and asynchronous updating in cellular automata. Biosystems 51:123–143CrossRefGoogle Scholar
  55. 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, Chennai, India, pp 39–49Google Scholar
  56. Sethi B, Roy S, Das S (2016) Asynchronous cellular automata and pattern classification. Complexity 21:370–386ADSMathSciNetCrossRefGoogle Scholar
  57. Silva F, Correia L (2013) An experimental study of noise and asynchrony in elementary cellular automata with sampling compensation. Nat Comput 12(4):573–588MathSciNetCrossRefGoogle Scholar
  58. 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–293Google Scholar
  59. Takada Y, Isokawa T, Peper F, Matsui N (2007a) Asynchronous self-reproducing loops with arbitration capability. Phys D Nonlinear Phenom 227(1):26–35ADSMathSciNetCrossRefzbMATHGoogle Scholar
  60. Takada Y, Isokawa T, Peper F, Matsui N (2007b) Asynchronous self-reproducing loops with arbitration capability. Phys D 227(1):26–35MathSciNetCrossRefzbMATHGoogle Scholar
  61. Vichniac GY (1984) Simulating physics with cellular automata. Phys D Nonlinear Phenom 10(1):96–116ADSMathSciNetCrossRefzbMATHGoogle Scholar
  62. Vielhaber M (2013) Computation of functions on n bits by asynchronous clocking of cellular automata. Nat Comput 12(3):307–322MathSciNetCrossRefzbMATHGoogle Scholar
  63. Wacker S, Worsch T (2013) On completeness and decidability of phase space invertible asynchronous cellular automata. Fundam Informaticae 126(2–3):157–181MathSciNetzbMATHGoogle Scholar
  64. Wolfram S (1985) Twenty problems in the theory of cellular automata. Phys Scr T9:170ADSMathSciNetCrossRefzbMATHGoogle Scholar
  65. Worsch T (2013) Towards intrinsically universal asynchronous CA. Nat Comput 12(4):539–550MathSciNetCrossRefzbMATHGoogle Scholar
  66. 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, Milan, Italy, pp 187–199Google Scholar

Copyright information

© Springer Science+Business Media LLC 2018

Authors and Affiliations

  1. 1.LORIA UMR 7503Inria Nancy – Grand EstNancyFrance