Update sequence stability in graph dynamical systems

Matthew Macauley; Henning S. Mortveit

doi:10.3934/dcdss.2011.4.1533

Article Contents

2011, Volume 4, Issue 6: 1533-1541. Doi: 10.3934/dcdss.2011.4.1533

This issue Previous Article Nongeneric bifurcations near heterodimensional cycles with inclination flip in $\mathbb{R}^4$ Next Article Conjectures for the existence of an idempotent in $\omega $-polynomial algebras

Update sequence stability in graph dynamical systems

Matthew Macauley^1, and
Henning S. Mortveit^2,

1.
Department of Mathematical Sciences, Clemson University, Clemson, SC 29634
2.
Department of Mathematics, NDSSL, Virginia Bioinformatics Institute, Virginia Tech, Blacksburg, VA 24061

Received: April 30, 2009

Revised: October 31, 2009

Published: November 2011

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 93D99, 37B99; Secondary: 05C90.

Citation:

Related Papers

Cited by

References

[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.
[2]	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.
[3]	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.
[4]	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.
[5]	A. Björner and F. Brenti, "Combinatorics of Coxeter Groups,'' Springer-Verlag, New York, 2005.
[6]	B. Bollobàs, "Random Graphs,'' Cambridge University Press, 2001.
[7]	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.
[8]	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.
[9]	A. Å. Hansson, H. S. Mortveit and C. M. Reidys, On asynchronous cellular automata, Adv. Complex Systems, 8 (2005), no. 4, 521-538.
[10]	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.
[11]	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.
[12]	V. S. A. Kumar, M. Macauley and H. S. Mortveit, Limit set reachability in asynchronous graph dynamical systems, RP 2009, 217-232.
[13]	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.
[14]	M. Macauley, J. McCammond and H. S. Mortveit, Order independence in asynchronous cellular automata, J. Cell. Autom., 3 (2008), 37-56.
[15]	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.
[16]	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.
[17]	H. S. Mortveit and C. M. Reidys, "An Introduction to Sequential Dynamical Systems," Universitext, Springer Verlag, 2007.
[18]	C. M. Reidys, Sequential dynamical systems over words, Ann. Comb., 10 (2006), 481-498.doi: 10.1007/s00026-006-0301-y.
[19]	C. M. Reidys, Combinatorics of sequential dynamical systems, Discrete Math., 308 (2007), 514-528.doi: 10.1016/j.disc.2007.03.033.
[20]	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.
[21]	S. Wolfram, "Theory and Applications of Cellular Automata," Adv. Ser. Complex Systems, 1, World Scientific Publishing Company, 1986.