# American Institute of Mathematical Sciences

October  2020, 40(10): 5765-5793. doi: 10.3934/dcds.2020245

## On the effects of firing memory in the dynamics of conjunctive networks

 1 Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Diagonal las Torres 2650, Peñalolen, Santiago, Chile, and, Unconventional Computing Laboratory, University of the West of England, Bristol, UK 2 Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Diagonal las Torres 2650, Peñalolen, Santiago, Chile 3 Departamento de Ingeniería Matemática, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Beauchef 851, Torre Norte, Piso 5, Santiago, Chile, and, Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France

* Corresponding author: Pedro Montealegre

Some of the results of this paper have been presented in the 25th International Workshop on Cellular Automata and Discrete Complex Systems AUTOMATA 2019.

Received  July 2019 Revised  February 2020 Published  June 2020

A boolean network is a map $F:\{0,1\}^n \to \{0,1\}^n$ that defines a discrete dynamical system by the subsequent iterations of $F$. Nevertheless, it is thought that this definition is not always reliable in the context of applications, especially in biology. Concerning this issue, models based in the concept of adding asynchronicity to the dynamics were propose. Particularly, we are interested in a approach based in the concept of delay. We focus in a specific type of delay called firing memory and it effects in the dynamics of symmetric (non-directed) conjunctive networks. We find, in the caseis in which the implementation of the delay is not uniform, that all the complexity of the dynamics is somehow encapsulated in the component in which the delay has effect. Thus, we show, in the homogeneous case, that it is possible to exhibit attractors of non-polynomial period. In addition, we study the prediction problem consisting in, given an initial condition, determinate if a fixed coordinate will eventually change its state. We find again that in the non-homogeneous case all the complexity is determined by the component that is affected by the delay and we conclude in the homogeneous case that this problem is PSPACE-complete.

Citation: Eric Goles, Pedro Montealegre, Martín Ríos-Wilson. On the effects of firing memory in the dynamics of conjunctive networks. Discrete & Continuous Dynamical Systems - A, 2020, 40 (10) : 5765-5793. doi: 10.3934/dcds.2020245
##### References:

show all references

##### References:
Symmetric conjunctive network ($F(x_0,x_1,x_2) = (x_1\land x_2, x_0\land x_2, x_0 \land x_1)$) dynamics in three vertices
Symmetric AND ($F(x_0,x_1,x_2) = (x_1\land x_2, x_0\land x_2, x_0 \land x_1)$) dynamics with firing memory $dt_i = 2, \text{ } i = 0,1,2$ in three vertices
Structure of a network $G^{\tau,k}$ in which the connected component $D$ has maximum delay $\tau \geq 2$ in every node and the connected component $G$ has maximum delay $\tau = 1$ in every node. Additionally, the subset $\partial$ contains every node in $D$ whose have a neighbour in $G$. (a).- The connected component $G$ has an arbiratry topology. (b).- The connected component $G$ is a bipartite graph. As it is shown in Proposition 1, the structure of $G$ may condition the existance of different type of attractors for a conjunctive network
A scheme of the dynamics of a node $i \in \partial$ that is in state 0 in some time step t. Note that before the sequence of states Ï„; Ï„ âˆ' 1;...; 0 we donâ€™t know the state of i and we note it as? in order to illustrate this situation. As a consequence of the fact that the maximum delay Ï„ is even together with the fact that two nodes in state 0 can not be neighbours we have that there are no attractor different from the fixed points $\overrightarrow 1$ and $\overrightarrow 0$.
(a) A network $G^{\tau,k}$ with maximum delay $\tau = 3$ and $10$ nodes exhibiting an attractor of period $8$. This network is defined by connecting the network $D$ (squares and non-colored circles) to a component with maximum delay $\tau = 1$ in every vertex (gray nodes). The nodes $1$ and $2$ (in grey) are the only nodes in $G^{\tau,k}$ with maximum delay $\tau = 1$. In addition, nodes represented by squares and non-coloured circles have maximum delay $\tau = 3$. Finally, nodes represented by squares are the nodes in the interface between the component $D$ and $G$ (we called this set $\partial$ in the latter section), and nodes represented by non-coloured circles are the ones that have no neighbours in $G$. (b) Configuration of an attractor with period $8$ defined over the network showed in (a)
Attractors with period $p = \tau +1$ for $\tau = 2$ and $\tau = 3$
Structure of the $j$-th block used in Proposition 5 to define a conjunctive network with firing memory and maximum delay values $dt_i = \tau$ for every node $i$ that admits attractors with period $k(\tau+1)$. Every circle in the figure represents clock $C(B_j)_{r,l}$ associated to a node $r$ represented by a square. This gadget has $\tau + 1$ nodes and every node has $\tau -1$ clocks
Initial condition for the j-th block, j â‰¥ 2 used in Proposition 5 to define an attractor with period k(Ï„ + 1): For the first block we just define the state of the first node to 0 instead of Ï„.
Interaction graph G associated to a conjunctive network with firing memory and maximum delay dti = Ï„ for all $i \in V\left( G \right)$, defined in Proposition 5 that admits attractors with length k(Ï„ + 1).
Structure of a block used in Proposition 5 to define a conjunctive network with firing memory and maximum delay values $dt_i = \tau$ for every node $i$ that admits attractors with period $k(\tau+1)$. Every circle in the figure represents clock associated to a node $r$ represented by a square. This gadget has $\tau + 1$ nodes and every node has $\tau -1$ clocks
Interaction graph $G$ associated to a conjunctive network with firing memory and maximum delay values $dt_i = \tau$ for every node $i \in V(G)$ that admits attractors with non polynomial period. Every component defines a local dynamics with period $(\tau + 1) p_i$. Initial condition is defined verifying that there are no connected nodes in $0$. Global period of the network is given by the product of prime numbers $p_i$.
Interaction graph associated to a conjunctive network with firing memory and maximum delay vector $dt_i = 2$ for every node $i$ that simulates an iterated monotone boolean circuit $C$. Layers are made up by AND or OR gates exclusively, using the gadgets shown in Figure 13 and Figure 14 are alternately ordered
Gadget of AND gates used in the graph shown in Figure 12. Signals are transmitted and coded based on the block gadget
Gadget of OR gates used in the graph shown in Figure 12. Signals are transmitted and coded based on the block gadget
Iterations of the AND gate gadget. A $0$ and a $1$ are computed as inputs. After seven steps the information is transmitted and initial condition is recovered.
Iterations of the OR gate gadget. A $0$ and a $1$ are computed as inputs. After three steps the information is transmitted and the initial condition is recovered.
 [1] Emma D'Aniello, Saber Elaydi. The structure of $\omega$-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195 [2] Khosro Sayevand, Valeyollah Moradi. A robust computational framework for analyzing fractional dynamical systems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021022 [3] Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205 [4] Hailing Xuan, Xiaoliang Cheng. Numerical analysis of a thermal frictional contact problem with long memory. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021031 [5] Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087 [6] Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028 [7] Elena K. Kostousova. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021015 [8] Juan Manuel Pastor, Javier García-Algarra, José M. Iriondo, José J. Ramasco, Javier Galeano. Dragging in mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 37-52. doi: 10.3934/nhm.2015.10.37 [9] Gheorghe Craciun, Jiaxin Jin, Polly Y. Yu. Single-target networks. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021065 [10] Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136 [11] Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089 [12] Alessandro Gondolo, Fernando Guevara Vasquez. Characterization and synthesis of Rayleigh damped elastodynamic networks. Networks & Heterogeneous Media, 2014, 9 (2) : 299-314. doi: 10.3934/nhm.2014.9.299 [13] Juan Manuel Pastor, Javier García-Algarra, Javier Galeano, José María Iriondo, José J. Ramasco. A simple and bounded model of population dynamics for mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 53-70. doi: 10.3934/nhm.2015.10.53 [14] Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367 [15] Mansour Shrahili, Ravi Shanker Dubey, Ahmed Shafay. Inclusion of fading memory to Banister model of changes in physical condition. Discrete & Continuous Dynamical Systems - S, 2020, 13 (3) : 881-888. doi: 10.3934/dcdss.2020051 [16] Jingni Guo, Junxiang Xu, Zhenggang He, Wei Liao. Research on cascading failure modes and attack strategies of multimodal transport network. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2020159 [17] Andrey Kovtanyuk, Alexander Chebotarev, Nikolai Botkin, Varvara Turova, Irina Sidorenko, Renée Lampe. Modeling the pressure distribution in a spatially averaged cerebral capillary network. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021016 [18] Chin-Chin Wu. Existence of traveling wavefront for discrete bistable competition model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 973-984. doi: 10.3934/dcdsb.2011.16.973 [19] Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355 [20] M. R. S. Kulenović, J. Marcotte, O. Merino. Properties of basins of attraction for planar discrete cooperative maps. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2721-2737. doi: 10.3934/dcdsb.2020202

2019 Impact Factor: 1.338