×

On the dynamics of semilattice networks. (English) Zbl 1492.94221

Let \(X=\{x_1,\ldots ,x_n\}\) be a finite set of \(n\) elements. A finite dynamical system is a map of the form \(f=(f_1,\ldots ,f_n):X^n\rightarrow X^n\). Finite dynamical systems are a computational tool to model networks of interacting entities. These discrete models are used to solve many problems in different areas of sciences and engineering. Two useful tools to study finite dynamical systems are dependency graphs and adjacency matrices. More precisely, given a finite dynamical system \(f\), we can associate a directed graph to \(f\) whose vertex set is \(\{1,\ldots ,n\}\) (each \(i\) corresponds to \(x_i\in X\)) and each pair \((i,j)\) of vertices is a directed edge if \(f_j\) depends on \(x_i\). In a similar way one can define the adjacency matrix associated to \(f\).
Now, let \(\wedge: X^2\rightarrow X\) be a semilattice operator. A finite dynamical system \(f\) is called a semilattice network if \(f_j=\wedge_{x_i\in I_j}x_i\) where \(I_j\) is the set of variables that influence the variable \(x_j\). A limit cycle of length \(t\) is a set with \(t\) elements \(\{\mathbf{u}_1,\ldots ,\mathbf{u}_t\}\subset X^n\) such that \(f (\mathbf{u}_i) = \mathbf{u}_{i+1}\) for \(i=1,\ldots ,t-1\) and \(f (\mathbf{u}_t) = \mathbf{ u}_{1}\). If \(t=1\) then \(\mathbf{u}_1\) is called a fixed point of \(f\) and if all limit cycles of \(f\) have length \(1\) then \(f\) is called a fixed-point network.
In this paper, the authors study the connections between cycle structure of a semilattice network and its dependency graph. In particular, they show that:
1.
the period of any limit cycle divides the loop number,
2.
all periodic points of a semilattice network are fixed points if and only if the loop number of dependency graph is 1.

MSC:

94C05 Analytic circuit theory
54H25 Fixed-point and coincidence theorems (topological aspects)
68R10 Graph theory (including graph drawing) in computer science
37E15 Combinatorial dynamics (types of periodic orbits)
Full Text: DOI

References:

[1] Ackerman, N. L.; Freer, C. E., Graph Turing machines, (Proceedings of WoLLIC 2017. Proceedings of WoLLIC 2017, LNCS, vol. 10388 (2017)), 1-13 · Zbl 1491.68068
[2] Adiga, A.; Kuhlman, C. J.; Marathe, M. V.; Mortveit, H. S.; Ravi, S. S.; Vullikanti, A., Graphical dynamical systems and their applications to bio-social systems, Int. J. Adv. Eng. Sci. Appl. Math., 11, 153-171 (2019)
[3] Barrett, C. L.; Chen, W. Y.C.; Zheng, M. J., Discrete dynamical systems on graphs and Boolean functions, Math. Comput. Simul., 66, 487-497 (2004) · Zbl 1113.37005
[4] Barrett, C. L.; Reidys, C. M., Elements of a theory of computer simulation I, Appl. Math. Comput., 98, 241-259 (1999) · Zbl 0927.68114
[5] Barrett, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of computer simulation II, Appl. Math. Comput., 107, 121-136 (2002) · Zbl 1049.68149
[6] Barrett, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of computer simulation III, Appl. Math. Comput., 122, 325-340 (2002) · Zbl 1050.68161
[7] 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) · Zbl 1028.37010
[8] Cardell, S. D.; Fúster-Sabater, A., Binomial representation of cryptographic binary sequences and its relation to cellular automata, Complexity, 2019, Article 2108014 pp. (2019) · Zbl 1421.94029
[9] 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) · Zbl 1333.05026
[10] Chiaselotti, G.; Gentile, T.; Oliverio, P. A., Parallel and sequential dynamics of two discrete models of signed integer partitions, Appl. Math. Comput., 232, 1249-1261 (2014) · Zbl 1410.37015
[11] Chen, X.; Gao, Z.; Başar, T., Asymptotic behavior of conjunctive Boolean networks over weakly connected digraphs, IEEE Trans. Autom. Control, 65, 6, 2536-2549 (June 2020) · Zbl 1533.93324
[12] Chopard, B.; Droz, M., Cellular Automata for Modeling Physics (1998), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0935.82561
[13] Colón-Reyes, O.; Laubenbacher, R.; Pareigis, B., Boolean monomial dynamical systems, Ann. Comb., 8, 425-439 (2004) · Zbl 1108.37007
[14] Defant, C., Binary codes and 2-periodic orbits of sequential dynamical system, Discrete Math. Theor. Comput. Sci., 19, 3, 10 (2017) · Zbl 1406.37035
[15] Deutsch, A.; Dormann, S., Cellular Automaton Modelling of Biological Pattern Formation (2004), Birkhäuser: Birkhäuser Boston
[16] Fúster-Sabater, A.; Caballero-Gil, P., On the use of cellular automata in symmetric cryptography, Acta Appl. Math., 93, 215-236 (2006) · Zbl 1151.94011
[17] Gao, Z.; Chen, X.; Liu, T.; Baar, T., Periodic behavior of a diffusion model over directed graphs, (2016 IEEE 55th Conference on Decision and Control (CDC) (2016)), 37-42
[18] Gao, Z.; Chen, X.; Başar, T., Stability structures of conjunctive Boolean networks, Automatica, 89, 8-20 (2018) · Zbl 1387.93092
[19] Gershenson, C., Classification of random Boolean networks, (Standish, R. K.; Bedau, M.; Abbass, H., Artifcial Life VIII 1-8 (2002), MIT Press: MIT Press Massachusets)
[20] Gershenson, C., Introduction to random Boolean networks (2004)
[21] Ilachinski, A., Cellular Automata: A Discrete Universe (2001), World Scientific: World Scientific Singapore · Zbl 1031.68081
[22] Jarrah, A. S.; Laubenbacher, R.; Veliz-Cuba, A., The dynamics of conjunctive and disjunctive Boolean network models, Bull. Math. Biol., 72, 1425-1447 (2010) · Zbl 1198.92018
[23] Jian, F.; Dandan, S., Complex network theory and its application research on P2P networks, Appl. Math. Nonlinear Sci., 1, 1, 45-52 (2016) · Zbl 1423.68052
[24] Kauffman, S. A., Metabolic stability and epigenesis in randomly constructed genetic nets, J. Theor. Biol., 22, 437-467 (1969)
[25] Kauffman, S. A., The Origins of Order: Self Organization and Selection in Evolution (1993), Oxford University Press
[26] Kawachi, A.; Ogihara, M.; Uchizawa, K., Generalized predecessor existence problems for Boolean finite dynamical systems, (Paper Presented at the Leibniz International Proceedings in Informatics. Paper Presented at the Leibniz International Proceedings in Informatics, LIPIcs (2017)), 83 · Zbl 1441.68140
[27] Kawachi, A.; Ogihara, M.; Uchizawa, K., Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs, Theor. Comput. Sci., 762, 25-40 (2019) · Zbl 1434.68315
[28] Kier, L. B.; Seybold, P. G.; Cheng, C-K., Modeling Chemical Systems Using Cellular Automata (2005), Springer: Springer New York
[29] Kosub, S., Dichotomy results for fixed-point existence problems for Boolean dynamical systems, Math. Comput. Sci., 1, 3, 487-505 (2008) · Zbl 1138.68034
[30] Kosub, S.; Homan, C. M., Dichotomy results for fixed point counting in Boolean dynamical systems, (Proceedings of the Tenth Italian Conference on Theoretical Computer Science. Proceedings of the Tenth Italian Conference on Theoretical Computer Science, ICTCS 2007 (2007)), 163-174
[31] Nandi, S.; Kar, B. K.; Chaudhuri, P. P., Theory and applications of cellular automata in cryptography, IEEE Trans. Comput., 43, 12, Article 13461357 pp. (1994)
[32] Ogihara, M.; Uchizawa, K., Computational complexity studies of synchronous Boolean finite dynamical systems, (Jain, R.; Jain, S.; Stephan, F., Theory and Applications of Models of Computation. Theory and Applications of Models of Computation, TAMC 2015. Theory and Applications of Models of Computation. Theory and Applications of Models of Computation, TAMC 2015, Lecture Notes in Computer Science, vol. 9076 (2015), Springer: Springer Cham) · Zbl 1459.68084
[33] Ogihara, M.; Uchizawa, K., Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs, Inf. Comput., 256, 226-236 (2017) · Zbl 1376.68068
[34] Schutter, B. D.; Moor, B. D., On the sequence of consecutive powers of a matrix in a Boolean algebra, SIAM J. Matrix Anal. Appl., 21, 328-354 (2000) · Zbl 0949.93051
[35] Shmulevich, I.; Dougherty, E. R.; Zhang, W., From Boolean to probabilistic Boolean networks as models of genetic regulatory networks, Proc. IEEE, 90, 1778-1792 (2002)
[36] Thomas, R., Boolean formalisation of genetic control circuits, J. Theor. Biol., 42, 563-585 (1973)
[37] Toffoli, T., Cellular automata as an alternative to (rather than an approximation of) differential equations in modeling physics, Physica D, 10, 117-127 (1984) · Zbl 0563.68054
[38] Toroczkai, Z.; Guclu, H., Proximity networks and epidemics, Physica A, 378, 68 (2007)
[39] Veliz-Cuba, A.; Laubenbacher, R., Dynamics of semilattice networks with strongly connected dependency graph, Automatica, 99, 167-174 (2019) · Zbl 1406.93197
[40] Wolfram, S., Statistical mechanics of cellular automata, Rev. Mod. Phys., 55, 3, 601-644 (1983) · Zbl 1174.82319
[41] Wolfram, S., Theory and Applications of Cellular Automata, Advanced Series on Complex Systems, vol. 1 (1986), World Scientific: World Scientific Singapore · Zbl 0609.68043
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.