Advanced Search
Article Contents
Article Contents

Update sequence stability in graph dynamical systems

Abstract Related Papers Cited by
  • In this article, we study finite dynamical systems defined over graphs, where the functions are applied asynchronously. Our goal is to quantify and understand stability of the dynamics with respect to the update sequence, and to relate this to structural properties of the graph. We introduce and analyze three different notions of update sequence stability, each capturing different aspects of the dynamics. When compared to each other, these stability concepts yield different conclusions regarding the relationship between stability and graph structure, painting a more complete picture of update sequence stability.
    Mathematics Subject Classification: Primary: 93D99, 37B99; Secondary: 05C90.


    \begin{equation} \\ \end{equation}
  • [1]

    C. L. Barrett, H. H. Hunt, M. V. Marathe, S. S. Ravi, D. Rosenkrantz, R. Stearns and P. Tosic, Gardens of Eden and fixed point in sequential dynamical systems, DM-CCG 2001, 95-110.


    C. L. Barrett, H. S. Mortveit and C. M. Reidys, Elements of a theory of simulation III: Equivalence of SDS, Appl. Math. Comput., 122 (2001), 325-340.doi: 10.1016/S0096-3003(00)00042-4.


    C. L. Barrett, H. S. Mortveit and C. M. Reidys, Elements of a theory of simulation IV: Fixed points, invertibility and equivalence, Appl. Math. Comput., 134 (2003), 153-172.doi: 10.1016/S0096-3003(01)00277-6.


    C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz and R. E. Stearns, Predecessor and permutation existence problems for sequential dynamical systems, DMTCS 2003, 69-80.


    A. Björner and F. Brenti, "Combinatorics of Coxeter Groups,'' Springer-Verlag, New York, 2005.


    B. Bollobàs, "Random Graphs,'' Cambridge University Press, 2001.


    R. Laubenbacher E. Sontag, A. Veliz-Cuba and A. Salam Jarrah, The effect of negative feedback loops on the dynamics of Boolean networks, Biophys. J., 95 (2008), 518-526.doi: 10.1529/biophysj.107.125021.


    D. L. Vertigan F. Jaeger and D. J. A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc. 108 (1990), 35-53.doi: 10.1017/S0305004100068936.


    A. Å. Hansson, H. S. Mortveit and C. M. Reidys, On asynchronous cellular automata, Adv. Complex Systems, 8 (2005), no. 4, 521-538.


    U. Karaoz, T. M. Murali, S. Letovsky, Y. Zheng, C. Ding, C. R. Cantor and S. Kasif, Whole-genome annotation by using evidence integration in functional-linkage networks, Proc. Nat. Acad. Sci., 101 (2004), 2888-2893.doi: 10.1073/pnas.0307326101.


    W. O. Kermack and A. G. McKendrick, A contribution to the mathematical theory of epidemics, Proc. Royal Soc. London A, 115 (1927), 700-721.doi: 10.1098/rspa.1927.0118.


    V. S. A. Kumar, M. Macauley and H. S. Mortveit, Limit set reachability in asynchronous graph dynamical systems, RP 2009, 217-232.


    M. Macauley, J. McCammond and H. S. Mortveit, Dynamics groups of asynchronous cellular automata, J. Algebraic Combinat, 33 (2011), 11-35.doi: 10.1007/s10801-010-0231-y.


    M. Macauley, J. McCammond and H. S. Mortveit, Order independence in asynchronous cellular automata, J. Cell. Autom., 3 (2008), 37-56.


    M. Macauley and H. S. Mortveit, On enumeration of conjugacy classes of Coxeter elements, Proc. Amer. Math. Soc., 136 (2008), 4157-4165.doi: 10.1090/S0002-9939-08-09543-9.


    M. Macauley and H. S. Mortveit, Cycle equivalence of graph dynamical systems, Nonlinearity, 22 (2009), 421-436.doi: 10.1088/0951-7715/22/2/010.


    H. S. Mortveit and C. M. Reidys, "An Introduction to Sequential Dynamical Systems," Universitext, Springer Verlag, 2007.


    C. M. Reidys, Sequential dynamical systems over words, Ann. Comb., 10 (2006), 481-498.doi: 10.1007/s00026-006-0301-y.


    C. M. Reidys, Combinatorics of sequential dynamical systems, Discrete Math., 308 (2007), 514-528.doi: 10.1016/j.disc.2007.03.033.


    I. Shmulevich, E. R. Dougherty and W. Zhang, From Boolean to probabilistic Boolean networks as models of genetic regulatory networks, Proc. IEEE, 90 (2002), 1778-1792.doi: 10.1109/JPROC.2002.804686.


    S. Wolfram, "Theory and Applications of Cellular Automata," Adv. Ser. Complex Systems, 1, World Scientific Publishing Company, 1986.

  • 加载中

Article Metrics

HTML views() PDF downloads(93) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint