On the dynamics of semilattice networks (Q2133914)

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: \begin{itemize} \item[1.] the period of any limit cycle divides the loop number, \item[2.] all periodic points of a semilattice network are fixed points if and only if the loop number of dependency graph is 1. \end{itemize}