Skip to main content
SpringerLink
Log in

Synchronism versus asynchronism in monotonic Boolean automata networks

  • Published:
Natural Computing Aims and scope Submit manuscript

Abstract

This paper focuses on Boolean automata networks and the updatings of automata states in these networks. More specifically, we study how synchronous updates impact on the global behaviour of a network. On this basis, we define different types of network sensitivity to synchronism, which are effectively satisfied by some networks. We also relate this synchronism-sensitivity to some properties of the structure of networks and to their underlying mechanisms.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  • Aldana M (2003) Boolean dynamics of networks with scale-free topology. Phys D 185:45–66

    Article  MathSciNet  MATH  Google Scholar 

  • Aracena J, Demongeot J, Goles E (2004a) On limit cycles of monotone functions with symmetric connection graph. Theor Comput Sci 322:237–244

    Article  MathSciNet  MATH  Google Scholar 

  • Aracena J, Demongeot J, Goles E (2004b) Positive and negative circuits in discrete neural networks. IEEE Trans Neural Netw 15:77–83

    Article  MATH  Google Scholar 

  • Chandesris J, Dennunzio A, Formenti E, Manzoni L (2011) Computational aspects of asynchronous cellular automata. In: Proceedings of DLT, lecture notes in computer science, vol 6795, pp 466–468. Springer, Berlin

  • Choffrut C (ed) (1988) Automata networks, lecture notes in computer science, vol 316. Springer, Berlin

  • Combe P, Nencka H (1997) Frustration and overblocking on graphs. Math Comput Model 26:307–309

    Article  MathSciNet  MATH  Google Scholar 

  • Cosnard M, Demongeot J (1985) Iteration theory and its functional equations, lecture notes in mathematics, vol 1163, chap. On the definition of attractors, Springer, Berlin, pp 23–31

  • Demongeot J, Goles E, Morvan M, Noual M, Sené S (2010) Attraction basins as gauges of robustness against boundary conditions in biological complex systems. PLoS ONE 5:e11,793

    Article  Google Scholar 

  • Derrida B, Pomeau Y (1986) Random networks of automata: a simple annealed approximation. Europhys Lett 1:45–49

    Article  Google Scholar 

  • Fatès N (2003) Experimental study of elementary cellular automata dynamics using the density parameter. Discret Math Theor Comput Sci AB:155–166

    MathSciNet  MATH  Google Scholar 

  • Floréen P (1992) Computational complexity problems in neural associative memories. PhD thesis, University of Helsinki

  • Goles E, Olivos J (1981) Comportement périodique des fonctions à seuil binaires et applications. Discret Appl Math 3:93–105

    Article  MATH  Google Scholar 

  • Goles E, Martínez S (1990) Neural and automata networks: dynamical behaviour and applications. Kluwer, Dordrecht

    Book  MATH  Google Scholar 

  • Goles E, Salinas L (2008) Comparison between parallel and serial dynamics of Boolean networks. Theor Comput Sci 396:247–253

    Article  MathSciNet  MATH  Google Scholar 

  • Harvey I, Bossomaier T (1997) Time out of joint: attractors in asynchronous random Boolean networks. In: Proceedings of ECAL, MIT Press, Cambridge, pp 67–75

  • Kauffman SA (1969) Metabolic stability and epigenesis in randomly constructed genetic nets. J Theor Biol 22:437–467

    Article  MathSciNet  Google Scholar 

  • Kleene SC (1956) Automata studies, annals of mathematics studies, vol 34, chap. Representation of events in nerve nets and finite automata, Princeton Universtity Press, Princeton, pp 3–41

  • Manzoni L (2012) Asynchronous cellular automata and dynamical properties. Natural Comput 11:269–276

    Article  MathSciNet  MATH  Google Scholar 

  • McCulloch WS, Pitts WH (1943) A logical calculus of the ideas immanent in nervous activity. Bull Math Biophys 5:115–133

    Article  MathSciNet  MATH  Google Scholar 

  • Noual M, Regnault D, Sené S (2012) Boolean networks synchronism sensitivity and XOR circulant networks convergence time. In: Full papers proceedings of AUTOMATA & JAC’2012, electronic proceedings in theoretical computer science, vol 90, Open Publishing Association, pp 37–52

  • Noual M, Regnault D, Sené S (2013) About non-monotony in Boolean automata networks. Theor Comput Sci 504:12–25

    Article  MathSciNet  MATH  Google Scholar 

  • Remy É, Ruet P (2008) From minimal signed circuits to the dynamics of Boolean regulatory networks. Bioinformatics 24:i220–i226

    Article  Google Scholar 

  • Richard A (2010) Negative circuits and sustained oscillations in asynchronous automata networks. Adv Appl Math 44:378–392

    Article  MathSciNet  MATH  Google Scholar 

  • Robert F (1986) Discret iterations: a metric study. Springer, Berlin

    Book  Google Scholar 

  • Saint Savage N (2005) The effects of state dependent and state independent probabilistic updating on Boolean network dynamics. PhD thesis, University of Manchester

  • Schabanel N, Regnault D, Thierry É (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 

  • Thieffry D, Thomas R (1995) Dynamical behaviour of biological regulatory networks-II. Immunity control in bacteriophage lambda. Bull Math Biol 57:277–297

    MATH  Google Scholar 

  • Thomas R (1973) Boolean formalization of genetic control circuits. J Theor Biol 42:563–585

    Article  Google Scholar 

  • Thomas R (1991) Regulatory networks seen as asynchronous automata: a logical description. J Theor Biol 153:1–23

    Article  Google Scholar 

  • Toulouse G (1977) Theory of the frustration effect in spin glasses. I. Commun Phys 2:115–119

    Google Scholar 

  • Vannimenus J, Toulouse G (1977) Theory of the frustration effect in spin glasses. II. Ising spins on a square lattice. J Phys C 10:L537–L542

    Article  Google Scholar 

  • von Neumann J (1966) Theory of self-reproducing automata. University of Illinois Press, Champaign

    Google Scholar 

Download references

Acknowledgements

This work has been partially supported by the project PACA APEX FRI.

Author information

Authors and Affiliations

  1. Freie Universität Berlin, FB Mathematik und Informatik, Berlin, Germany

    Mathilde Noual

  2. Aix-Marseille University, CNRS, LIF, Marseille, France

    Sylvain Sené

Authors
  1. Mathilde Noual
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sylvain Sené
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sylvain Sené.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Noual, M., Sené, S. Synchronism versus asynchronism in monotonic Boolean automata networks. Nat Comput 17, 393–402 (2018). https://doi.org/10.1007/s11047-016-9608-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11047-016-9608-8

Keywords

Search

Navigation