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

Figure 1.  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

Figure 2.  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

Figure 3.  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

Figure 4.  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 $.

Figure 5.  (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)

Figure 6.  Attractors with period $ p = \tau +1 $ for $ \tau = 2 $ and $ \tau = 3 $

Figure 7.  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

Figure 8.  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 Ï„.

Figure 9.  Interaction graph G associated to a conjunctive network with firing memory and maximum delay dt_i = Ï„ for all $i \in V\left( G \right)$, defined in Proposition 5 that admits attractors with length k(Ï„ + 1).

Figure 10.  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

Figure 11.  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 $.

Figure 12.  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

Figure 13.  Gadget of AND gates used in the graph shown in Figure 12. Signals are transmitted and coded based on the block gadget

Figure 14.  Gadget of OR gates used in the graph shown in Figure 12. Signals are transmitted and coded based on the block gadget

Figure 15.  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.

Figure 16.  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.