On periods and equilibria of computational sequential systems. (English) Zbl 1429.68167

Summary: In this paper, we show that sequential systems with (Boolean) maxterms and minterms as global evolution operators can present orbits of any period. Besides, we prove that periodic orbits with different periods greater than or equal to 2 can coexist. Nevertheless, when a sequential dynamical system has fixed points, we demonstrate that periodic orbits of other periods cannot appear. Finally, we provide conditions to obtain a fixed point theorem in this context. This work provides a relevant advance in the knowledge of the dynamics of such systems which constitute one of the most effective mathematical tools to model computational processes and other phenomena from other Sciences. Moreover, the ideas developed here could help to obtain similar results for other related systems.


68R10 Graph theory (including graph drawing) in computer science
37B15 Dynamical aspects of cellular automata
37E15 Combinatorial dynamics (types of periodic orbits)
68Q06 Networks and circuits as models of computation; circuit complexity
Full Text: DOI


[1] Abraham, F. D., A beginners guide to the nature and potentialities of dynamical and network theory II: a very brief comparison of discrete networks to continuous dynamical systems, Chaos Complex. Lett., 9, 2, 1-18 (2015)
[2] Aledo, J. A.; Diaz, L. G.; Martinez, S.; Valverde, J. C., On periods of parallel dynamical systems, Complexity 2017, 6 pages (2017)
[3] Aledo, J. A.; Martinez, S.; Pelayo, F. L.; Valverde, J. C., Parallel dynamical systems on maxterm and minterm Boolean functions, Math. Comput. Model., 35, 666-671 (2012)
[4] Aledo, J. A.; Martinez, S.; Valverde, J. C., Parallel discrete dynamical systems on independent local functions, J. Comput. Appl. Math., 237, 335-339 (2013)
[5] Aledo, J. A.; Martinez, S.; Valverde, J. C., Graph dynamical systems with general Boolean states, Appl. Math. Inf. Sci., 9, 1803-1808 (2015)
[6] Aracena, J.; Richard, A.; Salinas, L., Maximum number of fixed points in AND-OR-NOT networks, J. Comput. Syst. Sci., 80, 1175-1190 (2014)
[7] Barret, C. L.; Reidys, C. M., Elements of a theory of computer simulation I, Appl. Math. Comput., 98, 241-259 (1999)
[8] Barret, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of computer simulation II, Appl. Math. Comput., 107, 121-136 (2002)
[9] Barret, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of computer simulation III, Appl. Math. Comput., 122, 325-340 (2002)
[10] Barrett, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of computer simulation IV: sequential dynamical systems: fixed points, invertibility and equivalence, Appl. Math. Comput., 134, 153-171 (2003)
[11] Barret, C. L.; Chen, W. Y.C.; Zheng, M. J., Discrete dynamical systems on graphs and Boolean functions, Math. Comput. Simul., 66, 487-497 (2004)
[12] Barrett, C. L.; Hunt, H. B.; Marathe, M. V.; Ravi, S. S.; Rosenkrantz, D. J.; Stearns, R. E.; Tosic, P. T., Gardens of Eden and fixed points in sequential dynamical systems, Discrete Mathematics and Theoretical Computer Science Proceedings AA (DM-CCG), 95-110 (2001)
[13] Cattaneo, G.; Chiaselotti, G.; Oliverio, P. A.; Stumbo, F., A new discrete dynamical system of signed integer partitions, Eur. J. Comb., 55, 119-143 (2016)
[14] Chiaselotti, G.; Gentile, T.; A. Oliverio, P., Parallel and sequential dynamics of two discrete models of signed integer partitions, Appl. Math. Comput., 232, 1249-1261 (2014)
[15] Chopard, B.; Droz, M., Cellular Automata for Modeling Physics (1998), Cambridge University Press: Cambridge University Press Cambridge
[16] Deutsch, A.; Dormann, S., Cellular Automaton Modelling of Biological Pattern Formation (2004), Birkhäuser: Birkhäuser Boston
[17] Dieckman, U.; Law, R.; Metz, J. A.J., The Geometry of Ecological Interactions. Simplifying Spatial Complexity (2000), Cambridge University Press: Cambridge University Press Cambridge
[18] Fuster-Sabater, A.; Caballero-Gil, P., On the use of cellular automata in symmetric cryptography, Acta Appl. Math., 93, 215-236 (2006)
[19] Hardy, C., Networks of Meaning: A Bridge Between Mind and Matter (1998), Praeger: Praeger Michigan
[20] Hofbauer, J.; Sigmund, K., Evolutionary Games and Population Dynamics (2003), Cambridge University Press: Cambridge University Press Cambridge
[21] Hogeweg, P., Cellular automata as a paradigm for ecological modeling, Appl. Math. Comput., 27, 81-100 (1988)
[22] Jian, F.; Dandan, S., Complex network theory and its application research on P2P networks, Appl. Math. Nonlinear Sci., 1, 1, 45-52 (2016)
[23] Kauffman, S. A., Metabolic stability and epigenesis in randomly constructed genetic nets, J. Theor. Biol., 22, 437-467 (1969)
[24] Kauffman, S. A., Origins of Order: Self-Organization and Selection in Evolution (1993), Oxford University Press: Oxford University Press Oxford
[25] Kier, L. B.; Seybold, P. G.; Cheng, C.-K., Modeling Chemical Systems Using Cellular Automata (2005), Springer: Springer New York
[26] Mortveit, H. S.; Reidys, C. M., Discrete, sequential dynamical systems, Discrete Math., 226, 281-295 (2001)
[27] Mortveit, H. S.; Reidys, C. M., An Introduction to Sequential Dynamical Systems (2007), Springer: Springer New York
[28] Reydis, C. M., On acyclic orientations and sequential dynamical systems, Adv. Appl. Math., 27, 790-804 (2001)
[29] Sharkovsky, A. N., Co-existence of cycles of a continuous mapping of a line onto itself, Ukranian Math. Z., 16, 61-71 (1964)
[30] Tosic, P. T.; Agha, G. U., On computational complexity of counting fixed points in symmetric Boolean graph automata, Lect. Notes Comput. Sci., 3699, 191-205 (2005)
[31] Toroczkai, Z.; Guclu, H., Proximity networks and epidemics, Physica A, 378, 68 (2007)
[32] Veliz-Cuba, A.; Laubenbacher, R., On computation of fixed points in Boolean networks, J. Appl. Math. Comput., 39, 145-153 (2012)
[33] Wu, S.; Adig, A.; Mortveit, H. S., Limit cycle structure for dynamic bi-threshold systems, Theor. Comput. Sci., 559, 34-41 (2014)
[34] Wiggins, S., Introduction to Applied Nonlinear Systems and Chaos (1990), Springer: Springer New York
[35] Wolfram, S., Statistical mechanics of cellular automata, Rev. Mod. Phys., 55, 3, 601-644 (1983)
[36] Wolfram, S., Universality and complexity in cellular automata, Physica D, 10, 1-35 (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.