Abstract
We study the attractor structure of standard block-sequential threshold dynamical systems. In a block-sequential update, the vertex set of the graph is partitioned into blocks, and the blocks are updated sequentially while the vertices within each block are updated in parallel. There are several notable previous results concerning the two extreme cases of block-sequential update: (i) sequential and (ii) parallel. While parallel threshold systems can have limit cycles of length at most two, sequential systems can have only fixed points. However, Goles and Montealegre [5] showed the existence of block-sequential threshold systems that have arbitrarily long limit cycles. Motivated by this result, we study how the underlying graph structure influences the limit cycle structure of block-sequential systems. We derive a sufficient condition on the graph structure so that the system has only fixed points as limit cycles. We also identify several well-known graph families that satisfy this condition.
Chapter PDF
Similar content being viewed by others
References
Barrett, C.L., Hunt, H.B., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: Complexity of reachability problems for finite discrete dynamical systems. Journal of Computer and System Sciences 72(8), 1317–1345 (2006)
Diestel, R.: Graph Theory. Springer (2 edn.) (2000)
Goles, E., Olivos, J.: Comportement périodique des fonctions à seuil binaires et applications. Discrete Applied Mathematics 3(2), 93–105 (1981)
Goles, E., Martínez, S.: Neural and automata networks. Kluwer (1990)
Goles, E., Montealegre, P.: Computational complexity of threshold automata networks under different updating schemes. Theoretical Computer Science 559, 3–19 (2014). http://www.sciencedirect.com/science/article/pii/S0304397514006756. non-uniform Cellular Automata
Granovetter, M.: Threshold models of collective behavior. American journal of sociology, 1420–1443 (1978)
Karaoz, U., Murali, T., Letovsky, S., Zheng, Y., Ding, C., Cantor, C.R., Kasif, S.: Whole-genome annotation by using evidence integration in functional-linkage networks. Proceedings of the National Academy of Sciences of the United States of America 101(9), 2888–2893 (2004)
Kauffman, S.A.: Metabolic stability and epigenesis in randomly constructed genetic nets. Journal of theoretical biology 22(3), 437–467 (1969)
Kuhlman, C.J., Mortveit, H.S.: Limit sets of generalized, multi-threshold networks. Journal of Cellular Automata (2015)
Kuhlman, C.J., Mortveit, H.S., Murrugarra, D., Kumar, V.S.A.: Bifurcations in boolean networks. In: Automata 2011, pp. 29–46 (2011)
Macy, M.W.: Chains of cooperation: Threshold effects in collective action. American Sociological Review, 730–747 (1991)
Mortveit, H., Reidys, C.: An introduction to sequential dynamical systems. Springer Science & Business Media (2007)
Mortveit, H.S.: Limit cycle structure for block-sequential threshold systems. In: Sirakoulis, G.C., Bandini, S. (eds.) ACRI 2012. LNCS, vol. 7495, pp. 672–678. Springer, Heidelberg (2012)
Wu, S., Adiga, A., Mortveit, H.S.: Limit cycle structure for dynamic bi-threshold systems. Theoretical Computer Science (2014). http://www.sciencedirect.com/science/article/pii/S0304397514005088
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 IFIP International Federation for Information Processing
About this paper
Cite this paper
Adiga, A., Kuhlman, C.J., Mortveit, H.S., Wu, S. (2015). Effect of Graph Structure on the Limit Sets of Threshold Dynamical Systems. In: Kari, J. (eds) Cellular Automata and Discrete Complex Systems. AUTOMATA 2015. Lecture Notes in Computer Science(), vol 9099. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47221-7_5
Download citation
DOI: https://doi.org/10.1007/978-3-662-47221-7_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47220-0
Online ISBN: 978-3-662-47221-7
eBook Packages: Computer ScienceComputer Science (R0)