×

Parallel dynamical systems over graphs and related topics: a survey. (English) Zbl 1435.37024

Summary: In discrete processes, as computational or genetic ones, there are many entities and each entity has a state at a given time. The update of states of the entities constitutes an evolution in time of the system, that is, a discrete dynamical system. The relations among entities are usually represented by a graph. The update of the states is determined by the relations of the entities and some local functions which together constitute (global) evolution operator of the dynamical system. If the states of the entities are updated in a synchronous manner, the system is called a parallel dynamical system. This paper is devoted to review the main results on the dynamical behavior of parallel dynamical systems over graphs which constitute a generic tool for modeling discrete processes.

MSC:

37B15 Dynamical aspects of cellular automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Liu, C. L., Elements of Discrete Mathematics (1985), New York, NY, USA: McGraw-Hill, New York, NY, USA · Zbl 0592.00005
[2] Rosen, K., Discrete Mathematics and Its Applications (2011), Boca Raton, Fla, USA: McGraw-Hill, Boca Raton, Fla, USA
[3] Arrowsmith, D. K.; Place, C. M., An Introduction to Dynamical Systems (1990), Cambridge, UK: Cambridge University Press, Cambridge, UK · Zbl 0702.58002
[4] Devaney, R. L., An Introduction to Chaotic Dynamical Systems (1989), Ann Arbor, Mich, USA: Addison-Wesley, Ann Arbor, Mich, USA · Zbl 0695.58002
[5] Hirsch, M. W.; Smale, S., Differential Equations, Dynamical Systems and Linear Algebra (1974), New York, NY, USA: Academic Press, New York, NY, USA · Zbl 0309.34001
[6] Kuznetsov, Y. A., Elements of Applied Bifurcation Theory (2004), New York, NY, USA: Springer, New York, NY, USA · Zbl 1082.37002 · doi:10.1007/978-1-4757-3978-7
[7] Boole, G., An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities (1854), Cambridge, Mass, USA: Cambridge University Press, Cambridge, Mass, USA · Zbl 1205.03003
[8] Shannon, C. E., A symbolic analysis of relay and switching circuits [M.S. thesis] (1940), Cambridge, Mass, USA: MIT Press, Cambridge, Mass, USA
[9] Barrett, C. L.; Chen, W. Y.; Zheng, M. J., Discrete dynamical systems on graphs and Boolean functions, Mathematics and Computers in Simulation, 66, 6, 487-497 (2004) · Zbl 1113.37005 · doi:10.1016/j.matcom.2004.03.003
[10] Fúster-Sabater, A.; Caballero-Gil, P., On the use of cellular automata in symmetric cryptography, Acta Applicandae Mathematicae, 93, 1-3, 215-236 (2006) · Zbl 1151.94011 · doi:10.1007/s10440-006-9041-6
[11] Greil, F.; Drossel, B., Dynamics of critical Kauffman networks under asynchronous stochastic update, Physical Review Letters, 95, 4 (2005) · doi:10.1103/physrevlett.95.048701
[12] Nandi, S.; Kar, B. K.; Chaudhuri, P. P., Theory and applications of cellular automata in cryptography, IEEE Transactions on Computers, 43, 12, 1346-1357 (1994) · doi:10.1109/12.338094
[13] Roka, Z., Cellular automata on cayley graphs [Ph.D. thesis] (1994), Lyon, France: École Normale Supérieure de Lyon, Lyon, France · Zbl 0821.68087
[14] Shmulevich, I.; Dougherty, E. R.; Zhang, W., From boolean to probabilistic boolean networks as models of genetic regulatory networks, Proceedings of the IEEE, 90, 11, 1778-1792 (2002) · doi:10.1109/JPROC.2002.804686
[15] Toroczkai, Z.; Guclu, H., Proximity networks and epidemics, Physica A, 378, 1, 68-75 (2007) · doi:10.1016/j.physa.2006.11.088
[16] Ilachinski, A., Cellular Automata. A Discrete Universe (2001), Singapore: World Scientic, Singapore · Zbl 1031.68081
[17] Kari, J., Theory of cellular automata: a survey, Theoretical Computer Science, 334, 1-3, 3-33 (2005) · Zbl 1080.68070 · doi:10.1016/j.tcs.2004.11.021
[18] Maynard-Smith, J., Evolution and the Theory of Games (1982), Cambridge, Mass, USA: Cambridge University Press, Cambridge, Mass, USA · Zbl 0526.90102
[19] Sarkar, P., A brief history of cellular automata, ACM Computing Surveys, 32, 1, 80-107 (2000) · doi:10.1145/349194.349202
[20] Schiff, J. L., Cellular Automata (2008), New York, NY, USA: John Wiley & Sons, New York, NY, USA · Zbl 1142.68052
[21] Wolfram, S., Statistical mechanics of cellular automata, Reviews of Modern Physics, 55, 3, 601-644 (1983) · Zbl 1174.82319 · doi:10.1103/RevModPhys.55.601
[22] Wolfram, S., Universality and complexity in cellular automata, Physica D: Nonlinear Phenomena, 10, 1-2, 1-35 (1984) · Zbl 0562.68040 · doi:10.1016/0167-2789(84)90245-8
[23] Wolfram, S., Algebraic properties of cellular automata, Physica D, 10, 1-25 (1984)
[24] Wolfram, S., Theory and Applications of Cellular Automata. Theory and Applications of Cellular Automata, Advanced Series on Complex Systems, 1 (1986), Singapore: World Scientific Publishing, Singapore · Zbl 0609.68043
[25] Wolfram, S., Cellular Automata and Complexity (1994), New York, NY, USA: Addison-Wesley, New York, NY, USA · Zbl 0823.68003
[26] Kauffman, S. A., Metabolic stability and epigenesis in randomly constructed genetic nets, Journal of Theoretical Biology, 22, 3, 437-467 (1969) · doi:10.1016/0022-5193(69)90015-0
[27] Kauffman, S. A., Origins of Order: Self-Organization and Selection in Evolution (1993), Oxford, UK: Oxford University Press, Oxford, UK
[28] Serra, R.; Villani, M.; Agostini, L., On the dynamics of random Boolean networks with scale-free outgoing connections, Physica A: Statistical Mechanics and its Applications, 339, 3-4, 665-673 (2004) · doi:10.1016/j.physa.2004.03.026
[29] Shmulevich, I.; Kauffman, S. A., Activities and sensitivities in Boolean network models, Physical Review Letters, 93, 4 (2004) · doi:10.1103/physrevlett.93.048701
[30] von Neumann, J., Theory of Self-Reproducing Automata (1966), Chicago, Ill, USA: University of Illinois Press, Chicago, Ill, USA
[31] Gardner, M., The fantastic combination of John Conway’s new solitaire game ‘life’, Scientific American, 223, 120-123 (1970)
[32] Conway, J. H., What is life?, Winning Ways for Your Mathematical Plays (1982), New York, NY, USA: Academic Press, New York, NY, USA
[33] Barrett, C. L.; Reidys, C. M., Elements of a theory of computer simulation I: sequential CA over random graphs, Applied Mathematics and Computation, 98, 2-3, 241-259 (1999) · Zbl 0927.68114 · doi:10.1016/s0096-3003(97)10166-7
[34] Barret, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of computer simulation II, Applied Mathematics and Computation, 107, 121-136 (2002) · Zbl 1049.68149
[35] Barrett, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of simulation III: equivalence of SDS, Applied Mathematics and Computation, 122, 3, 325-340 (2001) · Zbl 1050.68161 · doi:10.1016/s0096-3003(00)00042-4
[36] Barrett, C. L.; Mortveit, H. S.; Reidys, C. M., ETS IV: sequential dynamical systems: fixed points, invertibility and equivalence, Applied Mathematics and Computation, 134, 1, 153-171 (2003) · Zbl 1028.37010 · doi:10.1016/s0096-3003(01)00277-6
[37] Bagrodia, A.; Chandy, K. M.; Liao, W. T., A unifying framework for distributed simulation, ACM Transactions on Modeling and Computer Simulation, 1, 4, 348-385 (1991) · Zbl 0842.68101 · doi:10.1145/130611.130614
[38] Jefferson, D., Virtual time, ACM Transactions on Programming Languages and Systems, 7, 3, 404-425 (1985) · doi:10.1145/3916.3988
[39] Kumar, R.; Garg, V., Modeling and Control of Logical Discrete Event Systems (1995), Dordrecht, The Netherlands: Kluwer Academic, Dordrecht, The Netherlands · Zbl 0875.68980
[40] Mortveit, H. S.; Reidys, C. M., Discrete, sequential dynamical systems, Discrete Mathematics, 226, 1-3, 281-295 (2001) · Zbl 1004.05056 · doi:10.1016/s0012-365x(00)00115-1
[41] Aledo, J. A.; Martínez, S.; Pelayo, F. L.; Valverde, J. C., Parallel discrete dynamical systems on maxterm and minterm Boolean functions, Mathematical and Computer Modelling, 55, 3-4, 666-671 (2012) · Zbl 1255.37003 · doi:10.1016/j.mcm.2011.08.040
[42] Aledo, J. A.; Martínez, S.; Valverde, J. C., Parallel dynamical systems over directed dependency graphs, Applied Mathematics and Computation, 219, 3, 1114-1119 (2012) · Zbl 1291.37018 · doi:10.1016/j.amc.2012.07.018
[43] Aledo, J. A.; Martínez, S.; Valverde, J. C., Parallel discrete dynamical systems on independent local functions, Journal of Computational and Applied Mathematics, 237, 1, 335-339 (2013) · Zbl 1248.37077 · doi:10.1016/j.cam.2012.06.002
[44] Laubenbacher, R.; Pareigis, B., Decomposition and simulation of sequential dynamical systems, Advances in Applied Mathematics, 30, 4, 655-678 (2003) · Zbl 1027.37049 · doi:10.1016/S0196-8858(02)00554-7
[45] Laubenbacher, R.; Pareigis, B., Update schedules of sequential dynamical systems, Discrete Applied Mathematics, 154, 6, 980-994 (2006) · Zbl 1134.37320 · doi:10.1016/j.dam.2005.10.010
[46] Mortveit, H. S.; Reidys, C. M., An Introduction to Sequential Dynamical Systems (2007), New York, NY, USA: Springer, New York, NY, USA
[47] Shmulevich, I.; Kauffman, S. A.; Aldana, M., Eukaryotic cells are dynamically ordered or critical but not chaotic, Proceedings of the National Academy of Sciences of the United States of America, 102, 38, 13439-13444 (2005) · doi:10.1073/pnas.0506771102
[48] Deutsch, A.; Dormann, S., Cellular Automaton Modelling of Biological Pattern Formation (2004), Boston, Mass, USA: Birkhäuser, Boston, Mass, USA
[49] Hogeweg, P., Cellular automata as a paradigm for ecological modeling, Applied Mathematics and Computation, 27, 1, 81-100 (1988) · Zbl 0646.92024 · doi:10.1016/0096-3003(88)90100-2
[50] Dieckman, U.; Law, R.; Metz, J. A. J., The Geometry of Ecological Interactions. Simplifying Spatial Complexity (2000), Cambridge, UK: Cambridge University Press, Cambridge, UK
[51] Hofbauer, J.; Sigmund, K., Evolutionary Games and Population Dynamics (2003), Cambridge, UK: Cambridge University Press, Cambridge, UK
[52] Chiaselotti, G.; Marino, G.; Oliverio, P. A.; Petrassi, D., A discrete dynamical model of signed partitions, Journal of Applied Mathematics, 2013 (2013) · Zbl 1266.06001 · doi:10.1155/2013/973501
[53] Bisi, C.; Chiaselotti, G., A class of lattices and boolean functions related to the Manickam-Miklös-Singhi conjecture, Advances in Geometry, 13, 1, 1-27 (2013) · Zbl 1259.05178 · doi:10.1515/advgeom-2012-0027
[54] Bisi, C.; Chiaselotti, G.; Oliverio, P. A., Sand piles models of signed partitions with \(d\) piles, ISRN Combinatorics, 2013 (2013) · Zbl 1264.05007 · doi:10.1155/2013/615703
[55] Chiaselotti, G.; Gentile, T.; Marino, G.; Oliverio, P. A., Parallel rank of two sandpile models of signed integer partitions, Journal of Applied Mathematics, 2013 (2013) · Zbl 1268.06001 · doi:10.1155/2013/292143
[56] Chiaselotti, G.; Gentile, T.; Oliverio, P. A., Parallel and sequential dynamics of two discrete models of signed integer partitions, Applied Mathematics and Computation, 232, 1249-1261 (2014) · Zbl 1410.37015 · doi:10.1016/j.amc.2014.01.118
[57] Chiaselotti, G.; Keith, W.; Oliverio, P. A., Two self-dual lattices of signed integer partitions, Applied Mathematics & Information Sciences, 8, 6, 3191-3199 (2014) · doi:10.12785/amis/080661
[58] Chopard, B.; Droz, M., Cellular Automata for Modeling Physics (1998), Cambridge, UK: Cambridge University Press, Cambridge, UK · Zbl 0973.82033 · doi:10.1017/cbo9780511549755
[59] Kier, L. B.; Seybold, P. G.; Cheng, C.-K., Modeling Chemical Systems Using Cellular Automata (2005), New York, NY, USA: Springer, New York, NY, USA
[60] Schnegg, M.; Stauffer, D., Dynamics of networks and opinions, International Journal of Bifurcation and Chaos, 17, 7, 2399-2409 (2007) · Zbl 1185.91147 · doi:10.1142/S0218127407018476
[61] Shelling, T. C., Dynamic models of segregation, Journal of Mathematical Sociology, 1, 143-186 (1971) · Zbl 1355.91061
[62] Rickert, M.; Nagel, K.; Schreckenberg, M.; Latour, A., Two lane traffic simulations using cellular automata, Physica A, 231, 4, 534-550 (1996) · doi:10.1016/0378-4371(95)00442-4
[63] Dorin, A., Boolean networks for the generation of rhythmic structure, Proceedings of the Australian Computer Music Conference
[64] Aledo, J. A.; Martínez, S.; Valverde, J. C., Parallel dynamical systems over special digraph classes, International Journal of Computer Mathematics, 90, 10, 2039-2048 (2013) · Zbl 1329.68177 · doi:10.1080/00207160.2012.742191
[65] Aledo, J. A.; Martínez, S.; Valverde, J. C., Graph dynamical systems with general boolean states, Applied Mathematics & Information Sciences, 9, 4, 1-6 (2015)
[66] Derrida, B.; Pomeau, Y., Randomnetworks of automata: a simple annealed approximation, Europhysics Letters, 1, 2, 45-49 (1986) · doi:10.1209/0295-5075/1/2/001
[67] Chen, W. Y. C.; Li, X.; Zheng, J., Matrix method for linear sequential dynamical systems on digraphs, Applied Mathematics and Computation, 160, 1, 197-212 (2005) · Zbl 1071.05039 · doi:10.1016/j.amc.2003.10.023
[68] Colón-Reyes, O.; Laubenbacher, R.; Pareigis, B., Boolean monomial dynamical systems, Annals of Combinatorics, 8, 4, 425-439 (2004) · Zbl 1108.37007 · doi:10.1007/s00026-004-0230-6
[69] Bender, E. A.; Williamson, S. G., A Short Course in Discrete Mathematics (2005), New York, NY, USA: Dover Publications, New York, NY, USA
[70] Morita, K., Reversible cellular automata, Journal of Information Processing, 35, 315-321 (1994)
[71] Toffoli, T.; Margolus, N. H., Invertible cellular automata: a review, Physica D: Nonlinear Phenomena, 45, 1-3, 229-253 (1990) · Zbl 0729.68066 · doi:10.1016/0167-2789(90)90185-r
[72] Wiggins, S., Introduction to Applied Nonlinear Systems and Chaos. Introduction to Applied Nonlinear Systems and Chaos, Texts in Applied Mathematics, 2 (1990), New York, NY, USA: Springer, New York, NY, USA · Zbl 0701.58001 · doi:10.1007/978-1-4757-4067-7
[73] Hernández Toledo, R. A., Linear finite dynamical systems, Communications in Algebra, 33, 9, 2977-2989 (2005) · Zbl 1097.37009 · doi:10.1081/agb-200066211
[74] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Reading, Mass, USA: Addison-Wesley, Reading, Mass, USA · Zbl 0426.68001
[75] Sipser, M., Introduction to the Theory of Computation (1997), Boston, Mass, USA: PWS Publishing Company, Boston, Mass, USA · Zbl 1169.68300
[76] Guirao, J. L.; Pelayo, F. L.; Valverde, J. C., Modeling the dynamics of concurrent computing systems, Computers & Mathematics with Applications, 61, 5, 1402-1406 (2011) · Zbl 1217.68150 · doi:10.1016/j.camwa.2011.01.008
[77] Pelayo, F. L.; Valverde, J. C., Notes on modeling the dynamics of concurrent computing systems, Computers & Mathematics with Applications, 64, 4, 661-663 (2012) · Zbl 1252.68204 · doi:10.1016/j.camwa.2011.12.079
[78] Reisig, W.; Rozenberg, G., Lectures on Petri Nets I: Basic Models: Advances in Petri Nets. Lectures on Petri Nets I: Basic Models: Advances in Petri Nets, Lecture Notes in Computer Science, 1491 (1998), New York, NY, USA: Springer, New York, NY, USA · Zbl 0903.00072
[79] Moore, E. F., Machine models of self-reproduction, Mathematical Problems in the Biological Sciences. Mathematical Problems in the Biological Sciences, Proceedings of Symposia in Applied Mathematics, 14, 17-33 (1962) · Zbl 0126.32408
[80] Hungerford, T. W., Algebra. Algebra, Graduate Texts in Mathematics, 73 (1974), New York, NY, USA: Springer, New York, NY, USA
[81] Gardner, M., On cellular automat, self-reproduction, the Garden of Eden and the game life, Scientic American, 224, 112-117 (1971)
[82] Toffoli, T., Cellular automata as an alternative to (rather than an approximation of) differential equations in modeling physics, Physica D, 10, 1-2, 117-127 (1984) · Zbl 0563.68054 · doi:10.1016/0167-2789(84)90254-9
[83] Toffoli, T.; Margolus, N., Cellular Automata Machines (1987), Cambridge, Mass, USA: MIT Press, Cambridge, Mass, USA · Zbl 0655.68055
[84] Blok, H. J.; Bergersen, B., Synchronous versus asynchronous updating in the ‘game of Life’, Physical Review E: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, 59, 4, 3876-3879 (1999)
[85] Mihaela, T.; Matache, T.; Heidel, J., Asynchronous random Boolean network model based on elementary cellular automata rule 126, Physical Review E, 71, 2, 1-13 (2005)
[86] Schönfisch, B.; de Roos, A., Synchronous and asynchronous updating in cellular automata, BioSystems, 51, 3, 123-143 (1999) · doi:10.1016/s0303-2647(99)00025-8
[87] Sole, R. V.; Luque, B.; Kauffman, S. A., Phase transitions in random networks with multiple states, 00-02-011 (2000), Santa Fe Institute
[88] Luque, B.; Ballesteros, F. J., Random walk networks, Physica A, 342, 1-2, 207-213 (2004) · doi:10.1016/j.physa.2004.04.080
[89] Shmulevich, I.; Dougherty, E. R., Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks (2010), Philadelphia, Pa, USA: SIAM, Philadelphia, Pa, USA · Zbl 1320.92020
[90] Aledo, J. A.; Martínez, S.; Valverde, J. C., Updating method for the computation of orbits in parallel and sequential dynamical systems, International Journal of Computer Mathematics, 90, 9, 1796-1808 (2013) · Zbl 1354.37045 · doi:10.1080/00207160.2013.767894
[91] Laubenbacher, R.; Pareigis, B., Equivalence relations on finite dynamical systems, Advances in Applied Mathematics, 26, 3, 237-251 (2001) · Zbl 0986.37028 · doi:10.1006/aama.2000.0717
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.