*Proof.* Let $Q = \{0,1\} \times \{0,1\} \cup \{e\}$ and denote by $\pi_1$ and $\pi_2$ the projections on the first and second components respectively for states in $\{0,1\} \times \{0,1\}$. We construct a family which essentially applies a majority rule on one component of composite states, it does synchronization checks using the second component, and use $e$ as an error state that spreads over the network. More precisely, consider the local map $\lambda: Q \times \mathbb{N}^Q \to Q$ that does the following at each node $v$:

* if $e$ appears in the neighborhood, then the image by $\lambda$ at $v$ is $e$;

* otherwise, let $M_1$ be the multiset of states of the $\pi_1$ components of states of neighbors and the node itself and denote by $m_1$ the state with a majority of occurrences in $M_1$ ($\pi_1$ of the state of $v$ in case of tie); then

- if all neighbors of node $v$ (including $v$) have the same $\pi_2$ component $b$, then the image by $\lambda$ at $v$ is $(m_1, 1-b)$;

- otherwise, the image by $\lambda$ at $v$ is $e$.

The CSAN family $\mathcal{F}$ we consider is the one defined by this local rule $\lambda$ at each node. Consider any automata network of the periodic update extension of $\mathcal{F}$ of period $p$, and consider any limit cycle of some of its orbits. We show that this limit cycle has length at most 2. There are two cases:

* if the update scheme is not a synchronous update scheme (all nodes update exactly at the same time steps), then there must be some time step at which a node $v$ is updated but some of its neighbors $v'$ isn't. So either $v$ updates to $e$ at this time step, or $v$ updates to a composite state with a $\pi_2$ component different from the $\pi_2$ component of $v'$. In the second case the next node to update among $v$ and $v'$ will update to $e$. Finally, since $e$ appears at some node in the orbit, this means that the limit cycle is the fixed point configuration everywhere equal to $e$.

* if the update scheme is the parallel update scheme, then: either $e$ appears in the considered orbit and the limit cycle is a fixed point; or $e$ never appears, which means that the $\pi_2$ component of nodes is oscillating between 0 and 1 and the behavior in the $\pi_1$ component is that of the classical majority rule with parallel update mode (which can only exhibit attractors of period at most 2 as shown in [16]), hence also of period at most 2.

We conclude that the family $\mathcal{F}_p$ has only limit cycles of length $\le 2$, whatever $p$.

If we consider now the non-symmetric version $\vec{\mathcal{F}}$, it is straightforward to build limit cycle of length $n$ (size of the network) using synchronized $\pi_2$ components. More precisely, if we consider a configuration $x$ such that the $\pi_2$ component is defined as 1 for every node in the graph, i.e. $\pi_2(x_v) = 1$ for all node $v$ then, each node will update its state following the classical majority rule in its $\pi_1$ component. In addition, the component $\pi_2$ will oscillate, meaning that $\pi_2(F(x)_v) = 0$ whenever $\pi_2(x_v) = 1$ and $\pi_2(F(x)_v) = 1$ whenever $\pi_2(x_v) = 0$.

Thus, we have that $\mathcal{F}_p$ cannot simulate $\vec{\mathcal{F}}$ (actually, it is not hard to show that $\vec{\mathcal{F}}$ is strongly universal since it admits coherent monotone gadgets). $\square$

Let us now give an example of CSAN family where the opposite situation occurs: periodic extensions are stronger than the non-symmetric version.

**Proposition 3.** There exists a CSAN family $\mathcal{F}$ such that its non-symmetric version $\vec{\mathcal{F}}$ admits only fixed points but for some $p \in \mathbb{N}$ its periodic update extension $\mathcal{F}_p$ admits attractors of non-constant period. As a consequence, there exists a CSAN family $\mathcal{F}$ such that its periodic update extension $\mathcal{F}_p$ for some $p$ cannot be simulated by its non-symmetric version $\vec{\mathcal{F}}$.

*Proof.* Consider any CSAN family $\mathcal{F}_0$ over alphabet $Q$ than can produce orbits with limit cycles of non-constant length over symmetric networks that are bipartite: one can for instance choose $\mathcal{F}_0$ to be the family of positive conjunctive networks under periodic update schedule of period 3 (see Theorem 21). Define a new alphabet $Q' = Q \cup Q \times \{0,1\} \cup \{e\}$ where we distinguish three types of states: *pure* states from $Q$, *composite* states from $Q \times \{0,1\}$ and the error state $e$. For a non-error state, its $Q$-content is either itself (when it is pure) or the projection on its $Q$ component (when it is composite). Let's define the family $\mathcal{F}$ by the following local behavior on any graph:
## 4.2. Locally positive symmetric conjunctive networks

In this section, we study a generalization of conjunctive networks that we call locally positive symmetric conjunctive networks. Using latter notation for CSAN families we denote this family by $\mathcal{F}_{\text{locally-pos}}$. In this particular case, we allow edges to have negative signs (which will switch the state of the corresponding neighbor) but with a local constraint: no neighborhood in which all the connections (remember that all edges are undirected) are negative is allowed. More precisely, a locally positive symmetric conjunctive network is a CSAN $(G, \lambda, \rho)$ in for any $v \in V(G)$ we have $\lambda_v(q, S) = \bigwedge_{q \in S} q$ and there exists $w \in N(v) : \rho(vw) = \text{Id}$.

We will show for this family that the threshold of universality when changing update modes is between block sequential update schemes and local clocks update schemes. More precisely, we show, on one hand, that the family remains dynamically constrained under block sequential schedule, and, on the other hand, we show that a local clocks version of this family is strongly universal because it admits coherent monotone gadgets. A similar construction will be used also for the general case in which we allow any kind of sign label over the edges of the network as we will show in next sections.

**Theorem 19.** Fix any $b \ge 1$ and consider $\mathcal{F}_{\text{locally-pos}}^{\text{BLOCK},b}$ the family of all locally positive symmetric conjunctive networks under block sequential schedule with at most $b$ blocks. Any orbit of any $F \in \mathcal{F}_{\text{locally-pos}}^{\text{BLOCK},b}$ reaches a cycle of length 1 or 2b in linear time (linear in the number of nodes). In particular, B-PRED and REACH problems for $\mathcal{F}_{\text{locally-pos}}^{\text{BLOCK},b}$ can be solved in polynomial time and the family is not universal.

*Proof.* Fix such an $F$ and denote by $E^+$ the set of its edges with positive sign. Recall that $F$ is a block sequential extension using alphabet $Q = \{0,1\} \times \{0, \dots, b-1\}$. To simplify notation, for any configuration $x$, we denote by $\alpha(x)$ its projection on the state component $\{0,1\}$ and by $\beta(x)$ its projection on the block component $\{0, \dots, b-1\}$. We say a configuration $x$ is *clean* if for any edge $(v_1, v_2) \in E^+$ it holds: if node $v_1$ updates strictly before node $v_2$ starting from $x$ (i.e. $\beta(x)_{v_1} < \beta(x)_{v_2}$) then $\alpha(x)_{v_1} \ge \alpha(x)_{v_2}$. First, one can remark that for any configuration $x$, the configuration $F^b(x)$ is clean. Indeed, the condition is trivial for edges of $E^+$ where both nodes update synchronously, and each time a node $v_1$ from an edge $(v_1, v_2) \in E^+$ updates strictly before the other then its state becomes no larger than $\alpha(x)_{v_2}$. Therefore, after a first update of $v_1$, the edge $(v_1, v_2)$ maintains the property for the remaining of the orbit that the next node to be updated has the maximum value among the pair.

Let us now consider an “energy” map giving to each edge $(v_1, v_2) \in E^+$ the energy $\mathcal{E}(x, v_1, v_2) = \alpha(x)_{v_1} + \alpha(x)_{v_2}$.

*Claim 1:* if $x$ is clean, then for any edge $(v_1, v_2) \in E^+$ it holds $\mathcal{E}(F(x), v_1, v_2) \le \mathcal{E}(x, v_1, v_2)$. If $v_1$ and $v_2$ update synchronously in one step, then $\alpha(F(x))_{v_1} \le \alpha(x)_{v_2}$ for $i \ne j \in \{1, 2\}$ so $\alpha(F(x))_{v_1} + \alpha(F(x))_{v_2} \le \alpha(x)_{v_1} + \alpha(x)_{v_2}$. If $v_1$ updates in one step and $v_2$ don't then

$$ \alpha(F(x))_{v_1} \le \alpha(x)_{v_2} \le \alpha(x)_{v_1}, $$

the last inequality being because $x$ is supposed clean. Thus $\mathcal{E}(F(x), v_1, v_2) \le \mathcal{E}(x, v_1, v_2)$ because $\alpha(F(x))_{v_2} = \alpha(x)_{v_2}$ in this case. The case where $v_2$ updates and $v_1$ doesn't is symmetric. If none of $v_1$ and $v_2$ update, their states don't change so the energy remains constant.
* $e$ states spread over the network, i.e. any node with an incoming neighbor in state $e$ updates to state $e$;

* if a node has a pure (resp. composite) state, then all its incoming neighbors must have a composite (resp. pure) state otherwise it updates to $e$ in one step; moreover, any pure state with some incoming neighbor in a state from $Q \times \{0\}$ will also update to $e$ (so when a node in a pure state is updated, all its incoming neighbors must be in a state from $Q \times \{1\}$ to prevent it from updating to $e$);

* outside the above cases, the type of a state doesn't change and

- if it is a pure state, its $Q$-content changes according to the local rules over $Q$ of the chosen CSAN family $\mathcal{F}_0$;

- if it is a composite state, its $\{0,1\}$ component is inverted (by $b \mapsto 1-b$), and its $Q$-content is updated according to the local rules over $Q$ as above, but only when the $\{0,1\}$ component is 1, otherwise the $Q$-content is left unchanged.

Now take any connected automata network from the non-symmetric version $\vec{\mathcal{F}}$ of the family we just defined. We claim that any orbit reaches a fixed-point. First, it is well-known (see [22]) that if the graph is acyclic, then all orbits converge to a fixed-point. So let's consider the case where the graph possesses a directed cycle $C$. Consider some configuration $x$, and let us show that $e$ must appear in the network at some step which implies that the orbit will reach a fixed-point. If the type of states does not alternate between pure and composite along cycle $C$, then $e$ is generated in one step. If the type of states correctly alternates in $C$ between pure and composite, then there must be a first step $t$ where some node of $C$ is in a composite state with value 0 on its $\{0,1\}$ component. Since $C$ is a cycle, this node is the incoming neighbor of some other node in a pure state. This last node will update to $e$ in this situation. This concludes the claim that any orbit reaches a fixed point in any network of $\vec{\mathcal{F}}$.

Let us now consider any bipartite symmetric network and some orbit of an automata network of family $\mathcal{F}_0$ reaching a long limit cycle. We can simulate any orbit starting from some $Q$-configuration $x$ by applying a periodic update scheme of period 2 to some automata network of family $\mathcal{F}$ on the same network as follows: by bi-partition of the network we can distribute the type of states (pure/composite) in such a way that no node has a neighbor with the same type as itself; then we update composite nodes at each step and pure nodes once every two steps (and start to update them at first step); we choose as initial configuration a configuration where the $Q$-contents correspond to $x$ and all composite node start with 1 in their $\{0,1\}$ component.

Thus, we have shown that the periodic extension of network admits attractors of non-constant period (because $\mathcal{F}_0$ satisfies this property and we have shown that the orbits of $\mathcal{F}_0$ can be simulated by $\mathcal{F}$ equipped with some periodic update scheme) and that the non-symmetric extension $\vec{\mathcal{F}}$ admits only fixed points. This shows that the periodic update extension of period 2 of $\mathcal{F}$ cannot be simulated by its non-symmetric version $\vec{\mathcal{F}}$. $\square$

# 6 Perspectives

The main results of this paper extend previous results [13, 15, 12] on the strong interplay between symmetry of local interactions and update modes. We showed how universality can be recovered from the symmetry constraint by allowing various degrees of asynchronism. An immediate question following our work is to find a natural example of a CSAN family which is (strongly) universal under periodic update schemes, but not universal under local clocks update schemes.

Besides universality, it would be interesting to better understand in general when a symmetric family can simulate its non-symmetric version under non-parallel update modes (as it was shown in Theorem 21). Here again, we are interested in the level of asynchronism required for this simulation to hold.

Another natural research direction is to try to further extend this analysis to other update modes. As we have pointed out in the update schemes section (see Remark 3), it would be interesting to study other types of update schemes which are not captured by general periodic update schemes such as firing memory schemes [13, 11], or other modes where the decision to apply an update at a node depends on its state (for instance we can interpret reaction-diffusion systems [8] as threshold networks with an update mode with memory). We can consider even more general ones inspired by the most permissive semantics studied in [4]. In some cases, Definition 12 of asynchronous extension should be adapted in order to capture latter update schemes.
**Claim 2:** if $x$ is clean and $\mathcal{E}(F^{2b}(x), v_1, v_2) = \mathcal{E}(x, v_1, v_2)$ for each $(v_1, v_2) \in E^+$ then $F^{2b}(x) = x$. By Claim 1, considering any edge $(v_1, v_2) \in E^+$, the sum of their states is constant during $2b$ steps. If $\alpha(x)_{v_1} = \alpha(x)_{v_2}$ then necessarily $F^{2b}(x)_{v_1} = x_{v_1}$ for $i = 1, 2$ because energy 0 (resp. 2) can only be realized by the pair of states $(0, 0)$ (resp. $(1, 1)$). If $\alpha(x)_{v_1} \neq \alpha(x)_{v_2}$ then necessarily $v_1$ and $v_2$ must swap their state synchronously to maintain the sum constant. This means that after $2b$ steps, they have done exactly two synchronous updates and they are back to the same state, thus we again have $F^{2b}(x)_{v_1} = x_{v_1}$. Since $E^+$ covers all vertices (property of the locally positive family $\mathcal{F}_{\text{locally-pos}}$), the property $F^{2b}(x)_v = x_v$ holds for all vertices. We conclude that $F^{2b}(x) = x$.

**Claim 3:** if $x$ is clean and $(v, v_1) \in E^+$ and $(v, v_2) \in E^+$ then $\mathcal{E}(F^{2b}(x), v, v_2) \le \mathcal{E}(x, v, v_1)$.

* if $\mathcal{E}(x, v, v_1) = 2$ the conclusion of the claim is obvious by definition;

* if $\mathcal{E}(x, v, v_1) = 1$ then

- either $\alpha(x)_v = 0$ and therefore $\alpha(F^b(x))_{v_2} = 0$ since $x$ is clean, so that $\mathcal{E}(F^b(x), v, v_2) \le 1$ and therefore $\mathcal{E}(F^{2b}(x), v, v_2) \le 1$ by Claim 1;

- or $\alpha(x)_{v_1} = 0$ and therefore $\alpha(F^{2b}(x))_{v_2} = 0$ because this time $\alpha(F^b(x))_v = 0$ (because $x$ is clean), so that $\mathcal{E}(F^{2b}(x), v, v_2) \le 1$;

* if $\mathcal{E}(x, v, v_1) = 0$ then $\alpha(x)_v = \alpha(x)_{v_1} = 0$ hence they will remain in state 0 forever, which implies that $\alpha(F^{2b}(x))_{v_2} = \alpha(F^{2b}(x))_v = 0$ so that $\mathcal{E}(F^{2b}(x), v, v_2) = 0$.

To conclude from the above claims, let $N^+(v)$ be the positive neighborhood of $v$, i.e. the set $N^+(v) = \{v' : (v, v') \in E^+\}$, and consider the following quantity on each vertex for a clean configuration $x$:

$$ \Phi(x, v) = \min_{v' \in N^+(v)} \{\mathcal{E}(x, v, v')\}. $$

Note that from Claim 1, $\Phi(F(x), v) \le \Phi(x, v)$ for any clean $x$. From Claim 3, for a clean $x$ and $(v_1, v_2) \in E^+$, it holds that $\mathcal{E}(F^{2b}(x), v_1, v_2) \le \Phi(x, v_1)$. Hence, if $\Phi(F^{4b}(x), v) = \Phi(x, v)$ for all vertices $v$, then $\mathcal{E}(F^{4b}(x), v_1, v_2) = \mathcal{E}(F^{2b}(x), v_1, v_2)$ for all $(v_1, v_2) \in E^+$ because

$$ \Phi(F^{4b}(x), v_1) \le \mathcal{E}(F^{4b}(x), v_1, v_2) \le \mathcal{E}(F^{2b}(x), v_1, v_2) \le \Phi(x, v_1). $$

In particular, from Claim 2, it implies $F^{4b}(x) = F^{2b}(x)$. Consider now the map $\mathcal{E}: Q^V \to \mathbb{N}$ giving to any configuration the "energy"

$$ \mathcal{E}(x) = \sum_{v \in V} \Phi(x, v) $$

which can only decrease along an orbit starting from a clean configuration, and whose maximum value is at most 2 times the number of nodes. We deduce from the above that if $x$ is clean and such that $\mathcal{E}(F^{4b}(x) = \mathcal{E}(x)$, then $F^{2b}(x)$ belongs to a periodic orbit of period at most $2b$ (and in fact either 1 or $2b$ since each node updates once every $b$ steps). On the other hand, the sequence $e_t = \mathcal{E}(F^{bt+1}(x))$ is decreasing for any configuration $x$ because $F^k(x)$ is clean for any $k$. The theorem follows (the consequence on B-PRED and REACH are straightforward and the non-universality follows from Theorem 6).

□
References

[1] J. Aracena, E. Goles, A. Moreira, and L. Salinas. On the robustness of update schedules in boolean networks. *Biosystems*, 97(1):1–8, jul 2009.

[2] J. Aracena, A. Richard, and L. Salinas. Fixed points in conjunctive networks and maximal independent sets in graph contractions. *J. Comput. System Sci.*, 88:145–163, 2017.

[3] Eric Goles Ch. and Pedro Montealegre. Computational complexity of threshold automata networks under different updating schemes. *Theor. Comput. Sci.*, 559:3–19, 2014.

[4] Thomas Chatain, Stefan Haar, Loïc Paulevé, et al. Most permissive semantics of boolean networks. *arXiv preprint arXiv:1808.10240*, 2018.

[5] Jacques Demongeot and Sylvain Sené. About block-parallel boolean networks: a position paper. *Nat. Comput.*, 19(1):5–13, 2020.

[6] Maximilien Gadouleau. On the influence of the interaction graph on a finite dynamical system. *Natural Com-puting*, 19(1):15–28, feb 2019.

[7] Maximilien Gadouleau and Søren Riis. Memoryless computation: new results, constructions, and extensions. *Theoretical Computer Science*, 562:129–145, January 2015.

[8] E. Goles and Martin Matamala. Reaction-diffusion automata: Three states implies universality. *Theory of Computing Systems*, 30(3):223–229, 1997.

[9] E. Goles and M. Noual. Disjunctive networks and update schedules. *Adv. Appl. Math.*, 48:646–662, 2012.

[10] E. Goles and J. Olivos. Periodic behaviour of generalized threshold functions. *Discrete Mathematics*, 30(2):187–219, 1980.

[11] Eric Goles, Fabiola Lobos, Gonzalo A. Ruz, and Sylvain Sené. Attractor landscapes in Boolean networks with firing memory. *Natural Computing*, 19:295–319, 2019.

[12] Eric Goles and Pedro Montealegre. Computational complexity of threshold automata networks under different updating schemes. *Theoretical Computer Science*, 559:3–19, 2014.

[13] Eric Goles, Pedro Montealegre, and Martín Ríos-Wilson. On the effects of firing memory in the dynamics of conjunctive networks. *Discrete & Continuous Dynamical Systems - A*, 40(10):5765–5793, 2020.

[14] Eric Goles, Pedro Montealegre, Ville Salo, and Ilkka Törmä. Pspace-completeness of majority automata networks. *Theor. Comput. Sci.*, 609:118–128, 2016.

[15] Eric Goles, Pedro Montealegre, Ville Salo, and Ilkka Törmä. Pspace-completeness of majority automata networks. *Theoretical Computer Science*, 609:118–128, 2016.

[16] E Goles-Chacc, F Fogelman-Soulie, and D Pellegrin. Decreasing energy functions as a tool for studying threshold networks. *Discrete Applied Mathematics*, 12(3):261–277, 1985.

[17] Stuart Kauffman. Homeostasis and differentiation in random genetic control networks. *Nature*, 224(5215):177–178, oct 1969.

[18] Warren S. McCulloch and Walter Pitts. A logical calculus of the ideas immanent in nervous activity. *The Bulletin of Mathematical Biophysics*, 5(4):115–133, dec 1943.

[19] Martín Ríos-Wilson and Guillaume Theyssier. Intrinsic universality in automata networks i: Families and simulations. *Theoretical Computer Science*, 997:114511, 2024.

[20] Martín Ríos-Wilson and Guillaume Theyssier. Intrinsic universality in automata networks ii: Glueing and gadgets. *Theoretical Computer Science*, page 114779, 2024.

[21] F. Robert. Blocs-h-matrices et convergence des methodes iteratives classiques par blocs. *Linear Algebra and its Applications*, 2(2):223–265, apr 1969.

[22] François Robert. Iterations sur des ensembles finis et automates cellulaires contractants. *Linear Algebra and its applications*, 29:393–412, 1980.
Now, we want to show that coherent AND/OR gadgets can be implemented in $\mathcal{F}_{\text{locally-pos}}^{\text{CLOCK},c}$, i.e. we want to show that this family has coherent monotone gadgets. However, in order to accomplish this task we need a construction that we will be using for the next subsection. Particularly, we need to implement the gadgets that are shown in Figures 13 and 14. Then, we will adapt latter gadgets in order to make it work for locally positive symmetric conjunctive networks. Thus, as a consequence, we will have that $\mathcal{F}_{\text{locally-pos}}^{\text{CLOCK},c}$ is strongly universal.

**Theorem 20.** There exist $c > 0$ such that the family $\mathcal{F}_{\text{locally-pos}}^{\text{CLOCK},c}$ of all locally positive symmetric conjunctive networks under local clocks update scheme with clock parameter $c$ has coherent monotone gadgets.

*Proof.* We start by observing that the gadgets in Figures 13 and 14 can be implemented in $\mathcal{F}_{\text{locally-pos}}^{\text{CLOCK},c}$ for some $c$. This can be easily done by adding a positive node to each node in the gadget. The main idea here is that each of these artificial positive nodes will play no role in calculations and will stay in state 1 most of the time. In fact, it suffices that these positive neighbors reach state 1 before critical steps of computation are performed inside the gadget.

In order to illustrate this idea, let us consider two different cases and analyze why computation gadget still works in this case:

1. **Nodes in 4-cycles:** observe that these nodes have a fixed trajectory that is independent on the input that computation part is handling. Thus, it suffices to note that each node in the context effectively changes its state (they are in an attractor of period $3 \times 3$ as it is shown in Figure 5). As a consequence of this latter observation, we can set the local period of each positive neighbor so it is updated when its neighbor in the clock is in state 1. More precisely, we fix the corresponding local period value to 9 and correctly initialize them so each positive neighbor is updated exactly when their correspondent node is in state 1.

2. **Central nodes:** Observe that, in this case, we have that in the pseudo-orbit given in Table 3 and Table 4 each node eventually reaches the state 1 independently from the value of $x, y, z, x'$ and $y'$. Thus, as same as the nodes that are in the 4-cycles, it suffices to set up the local clock of each positive neighbor in order to be updated while its neighbor in the gadget is in state 1. More precisely, it suffices to set up clocks following values in Table 3 and Table 4 and set clocks to be updated every 18 time-steps. Note that this work since nodes in the central part are in the first block so positive neighbors are updated at the same time as its neighbors but only when nodes in the gadget are in state 1.

Thus, gadgets in Figures 13 and 14 can be implemented as same as we did for general symmetric signed conjunctive networks and desired result holds.

□

Finally, as a direct consequence of latter theorem we have the following corollary:

**Corollary 2.** There exist $c > 0$ such that the family $\mathcal{F}_{\text{locally-pos}}^{\text{CLOCK},c}$ of all locally positive symmetric conjunctive networks under local clocks update scheme with clock parameter $c$ is strongly universal.
[23] Bart De Schutter and Bart De Moor. On the sequence of consecutive powers of a matrix in a boolean algebra. *SIAM Journal on Matrix Analysis and Applications*, 21(1):328–354, jan 1999.

[24] René Thomas. Boolean formalization of genetic control circuits. *Journal of Theoretical Biology*, 42(3):563–585, dec 1973.

[25] Angela Wu and Azriel Rosenfeld. Cellular graph automata. i. basic concepts, graph property measurement, closure properties. *Information and Control*, 42(3):305 – 329, 1979.

[26] Angela Wu and Azriel Rosenfeld. Cellular graph automata. ii. graph and subgraph isomorphism, graph structure recognition. *Information and Control*, 42:330–353, 09 1979.
### 4.3. All-positive networks

As same as we did in the previous sections, we use the notation: $\mathcal{F}_{\text{pos}}^{\text{PER},p}$, $\mathcal{F}_{\text{pos}}^{\text{CLOCK},c}$, $\mathcal{F}_{\text{pos}}^{\text{BLOCK},b}$. First, we observe that positive conjunctive networks being a particular case of symmetric threshold networks it follows from the classical results of [17, 16], that they always converge to some fixed point or cycle of length two under the parallel update scheme. Therefore they are not dynamically complex with parallel update schedule. It turns out that with a periodic update schedule of period 3 they can break this limitation and produce super-polynomial cycles.

Particularly, we show that positive conjunctive networks with a periodic update schedule of period 3 can break the previous limitation on attractor period and produce superpolynomial cycles. Observe that all the graphs over we are defining networks in this family (and also in the other concrete examples we will be exploring in next sections) are non-directed (symmetric). If we observe carefully the effect of periodic update schemes, we note that we are actually changing the interaction graph of the network by considering different orders for updating nodes and thus, breaking the symmetry in the different connections that nodes have in the network. Moreover, we corroborate this remark by showing that actually, we can simulate arbitrary conjunctive networks (defined over directed graphs) by using a periodic update scheme. We accomplish this by applying our formalism on simulation and gadget glueing. In fact, we show that the family of symmetric conjunctive networks admits coherent conjunctive gadgets and thus it is capable of simulating the family of directed (non-symmetric) networks. Particularly, this implies that this family admits attractors of superpolynomial period.

**Proposition 1.** Let $p \ge 1$ and denote by $\mathcal{F}_{\text{pos}}^{\text{PER},p}$ be the family of positive conjunctive networks under periodic update schedules of period $p$. Then, $\mathcal{F}_{\text{pos}}^{\text{PER},p}$ is not universal and therefore it does not admit coherent monotone gadgets.

*Proof.* We actually show that the longest transient of any $F \in \mathcal{F}$ with $n$ nodes is $O(n^2)$, then the conclusions follow by Theorems 6 and 8. Recall that the alphabet is $\{0,1\} \times \{0, \dots, p\} \times 2^{\{0, \dots, p\}}$ and, by definition, on any given configuration $x$ the component $\{0, \dots, p\} \times 2^{0, \dots, p}$ is periodic of period $p$ independently of the behavior on the first $\{0,1\}$ component. Moreover, the behavior on the $\{0,1\}$ component is that of a fixed (non-symmetric) conjunctive network $F'$ in the following sense:

$$F^{t+p}(x) = F'(F^t(x)), \forall t \ge 0.$$

By [23, Theorem 3.20], the transient of any orbit of $F'$ is $O(n^2)$. We deduce that the transient of the orbit of $x$ under $F$ is also $O(n^2)$. $\square$

**Theorem 21.** Let $\mathcal{F}_{\text{pos}}^{\text{PER},3}$ be the family of positive conjunctive networks under periodic update schedule of period 3. $\mathcal{F}_{\text{pos}}^{\text{PER},3}$ has coherent conjunctive gadgets and therefore simulates the family of directed conjunctive networks and for instance can produce superpolynomial cycles.

*Proof.* The conclusion about simulations of directed conjunctive networks and superpolynomial cycles follows from 10. We now describe the coherent conjunctive gadgets within family $\mathcal{F}_{\text{pos}}^{\text{PER},3}$ using notations from Definition 9. Let $F_{\text{COPY}} \in \mathcal{F}_{\text{pos}}^{\text{PER},3}$ be defined on the following graph with nodes $V_{\text{COPY}} = \{v_1, v_2, v_3, v_4, v_5, v'_4, v'_5\}$:
<figure><img src="image_17.png" /></figure>

Let also $F_{AND} \in \mathcal{F}$ be defined on the following graph with nodes $V_{AND} = \{v_1, v_2, v'_1, v'_2, v_3, v_4, v_5\}$:

<figure><img src="image_18.png" /></figure>

Recall that both $F_{COPY}$ and $F_{AND}$ have alphabet $Q = \{0,1\} \times \{0,1,2\} \times 2^{\{0,1,2\}}$. Now let $C = C_i \cup C_o$ be the glueing interface with $C_i = \{i\}$ and $C_o = \{o\}$. $F_{COPY}$ is seen as a gadget with one input and two outputs for the gate $COPY \in \mathcal{G}_{conj}$ as follows:

* $\phi_{COPY,1}^i(i) = v_2$ and $\phi_{COPY,1}^i(o) = v_1$;

* $\phi_{COPY,1}^o(i) = v_5$ and $\phi_{COPY,1}^o(o) = v_4$.

* $\phi_{COPY,2}^o(i) = v'_5$ and $\phi_{COPY,2}^o(o) = v'_4$.

$F_{AND}$ is seen as a gadget with two inputs and one output for the gate AND $\in \mathcal{G}_{conj}$ as follows:

* $\phi_{AND,1}^i(i) = v_2$ and $\phi_{AND,1}^i(o) = v_1$;

* $\phi_{AND,2}^i(i) = v'_2$ and $\phi_{AND,2}^i(o) = v'_1$.

* $\phi_{AND,1}^o(i) = v_5$ and $\phi_{AND,1}^o(o) = v_4$.

We now define the following elements required by Definition 9:

* the two state configurations $s_q$ for $q \in \{0,1\}$ are defined by $s_q(i) = (q,0,\{0,2\})$ and $s_q(o) = (1,0,\{0,1\})$;

* the context configuration is defined by $c(v_3) = (1,0,\{1,2\})$;

* the time constant is $T = 3$

* the standard trace $\tau_{q,q'}$ over the glueing interface from $q \in \{0,1\}$ to $q' \in \{0,1\}$ is given by:

<table><thead><tr><th>time</th><th><i>i</i></th><th><i>o</i></th></tr></thead><tbody><tr><td>0</td><td>(<i>q</i>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td></tr><tr><td>1</td><td>(1, 1, {0, 2})</td><td>(<i>q</i>, 1, {0, 1})</td></tr><tr><td>2</td><td>(1, 2, {0, 2})</td><td>(1, 2, {0, 1})</td></tr><tr><td>3</td><td>(<i>q</i>', 0, {0, 2})</td><td>(1, 0, {0, 1})</td></tr></tbody></table>

* for any $q_i, q_i^T, q_o, q_o' \in \{0,1\}$ we have the following $\{v_1, v_5, v'_5\}$-pseudo orbit for $F_{COPY}$:

<table><thead><tr><th>time</th><th><i>v</i><sub>1</sub></th><th><i>v</i><sub>2</sub></th><th><i>v</i><sub>3</sub></th><th><i>v</i><sub>4</sub></th><th><i>v</i><sub>5</sub></th><th><i>v</i>'<sub>4</sub></th><th><i>v</i>'<sub>5</sub></th></tr></thead><tbody><tr><td>0</td><td>(<i>q</i><sub>i</sub>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td><td>(1, 0, {1, 2})</td><td>(<i>q</i><sub>o</sub>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td><td>(<i>q</i>'<sub>o</sub>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td></tr><tr><td>1</td><td>(1, 1, {0, 2})</td><td>(<i>q</i><sub>i</sub>, 1, {0, 1})</td><td>(1, 1, {1, 2})</td><td>(1, 1, {0, 2})</td><td>(<i>q</i><sub>o</sub>, 1, {0, 1})</td><td>(1, 1, {0, 2})</td><td>(<i>q</i>'<sub>o</sub>, 1, {0, 1})</td></tr><tr><td>2</td><td>(1, 2, {0, 2})</td><td>(1, 2, {0, 1})</td><td>(<i>q</i><sub>i</sub>, 2, {1, 2})</td><td>(1, 2, {0, 2})</td><td>(1, 2, {0, 1})</td><td>(1, 2, {0, 2})</td><td>(1, 2, {0, 1})</td></tr><tr><td>3</td><td>(<i>q</i>'<sub>i</sub>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td><td>(1, 0, {1, 2})</td><td>(<i>q</i><sub>i</sub>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td><td>(<i>q</i><sub>i</sub>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td></tr></tbody></table>
• for any $q_i, q_i^T, q_{i'}, q_{i'}^T, q_o \in \{0, 1\}$ we have the following $\{v_1, v_1', v_5\}$-pseudo orbit for $F_{\text{AND}}$:

<table><thead><tr><th>time</th><th>v<sub>1</sub></th><th>v<sub>2</sub></th><th>v'<sub>1</sub></th><th>v'<sub>2</sub></th><th>v<sub>3</sub></th><th>v<sub>4</sub></th><th>v<sub>5</sub></th></tr></thead><tbody><tr><td>0</td><td>(q<sub>i</sub>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td><td>(q<sub>i'</sub>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td><td>(1, 0, {1, 2})</td><td>(q<sub>o</sub>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td></tr><tr><td>1</td><td>(1, 1, {0, 2})</td><td>(q<sub>i</sub>, 1, {0, 1})</td><td>(1, 1, {0, 2})</td><td>(q<sub>i'</sub>, 1, {0, 1})</td><td>(1, 1, {1, 2})</td><td>(1, 1, {0, 2})</td><td>(q<sub>o</sub>, 1, {0, 1})</td></tr><tr><td>2</td><td>(1, 2, {0, 2})</td><td>(1, 2, {0, 1})</td><td>(1, 2, {0, 2})</td><td>(1, 2, {0, 1})</td><td>(q<sub>i</sub> &amp; q<sub>i'</sub>, 2, {1, 2})</td><td>(1, 2, {0, 2})</td><td>(1, 2, {0, 1})</td></tr><tr><td>3</td><td>(q<sub>i</sub><sup>T</sup>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td><td>(q<sub>i'</sub><sup>T</sup>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td><td>(1, 0, {1, 2})</td><td>(q<sub>i</sub> &amp; q<sub>i'</sub>, 0, {0, 2})</td><td>(1, 0, {0, 1})</td></tr></tbody></table>

□

Interestingly, local clock update schedules on conjunctive networks are not able to produce superpolynomial cycles. To avoid to much conflicts in indices in notations, we denote by $x^Q$, $x^c$ and $x^m$ the three components of a configuration $x$ in some local clocks extension network.

**Lemma 22.** Let us fix any $c > 0$ and consider the family $\mathcal{F}_{\text{pos}}^{\text{CLOCK},c}$ of all positive conjunctive networks under local clocks update scheme with clock period $c$. Fix $n > 0$ and let $F: Q_c^n \to Q_c^n \in \mathcal{F}_{\text{pos}}^{\text{CLOCK},c}$. For any configuration $(x^Q, x^c, x^m) \in Q_c^n$ we have that the period of the attractor reached from $(x^Q, x^c, x^m)$ is at most $2 \text{lcm}\{x_v^m : v \in \{1, \dots, n\}\}$. Moreover, for each attractor $\bar{x} \in \text{Att}(F)$, the set of nodes whose $Q$ component is not constant in $\bar{x}$ induces a bipartite subgraph.

*Proof.* Let $(x^Q, x^c, x^m) \in Q_c^n$ be a configuration and $(\bar{x}^Q, \bar{x}^c, \bar{x}^m) \in \text{Att}(F)$ be an attractor that is reachable from $(x^Q, x^c, x^m)$ and that is not a fixed point, i.e. $p(\bar{x}) \ge 2$. In order to simplify the notation, we are going to denote $\bar{x}^Q$ by $\bar{x}$. Let $i \in \{0, \dots, n-1\}$ be a coordinate such that $\bar{x}_i$ changes its state, i.e there exists some $t \in \mathbb{N}$ such that $\bar{x}(0)_i \neq \bar{x}(t)_i$. Without loss of generality we assume that $\bar{x}(0)_i = 1$ and $\bar{x}^c(0)_i = 0$ and $\bar{x}(1)_i = 0$. Consider $t_1$ as the first time step such that the coordinate $i$ changes its state from 0 to 1, which means that, $t_1$ is the first time step such that $\bar{x}(t_1) = 0$ and $\bar{x}(t_1+1) = 1$. Observe that $t_1 = sx_i^m$ for some $s \ge 1$. Note that, for all $j \in N(i)$, $\bar{x}(t_1)_j = 1$. Moreover, we have that for all $j \in N(i)$: and that $\bar{x}(s)_j = 1$ for all $s \in [1, t_1]$ (see Figure 15). This is because, since the interaction graph is symmetric, $j$ cannot be in state 0 during interval $[1, t_1]$ otherwise both $i$ and $j$ would stay in state 0 forever, thus contradicting the hypothesis on $i$. We deduce that $x_j^m \ge t_1 = sx_i^m$ (otherwise $j$ would update its state and become 0 on interval $[1, t_1]$). Now consider $t_0$ to be the first time step in which the node $i$ changes its state from 1 to 0, i.e. $\bar{x}(t_0) = 1$ and $\bar{x}(t_0+1) = 0$. Observe that, $t_1 < t_0 = t_1 + s^*x_i^m$ for some $s^* \ge 1$. In addition, there must exist some neighbor $k \in N(i)$ satisfying that $\bar{x}(t_0)_k = 0$, otherwise $i$ cannot change to 0 (it requires at least one neighbor in 0 in order to change its state from 1 to 0). Observe that node $k$ satisfies $x_k^m \le x_i^m$ because it needs to update to 0 before node $i$. More precisely, by the definition of $t_0$ we have that $i$ is fixed in state between $t_1$ and $t_0$ (see Figure 15). Additionally, we have that $\bar{x}_k(t_1) = 1$, $\bar{x}_k(t_0) = 0$ and also we have that $\bar{x}(t_0 - x_i^m)_k = 1$ (otherwise it contradicts the minimality of $t_0$). Finally, since $i$ remains in state 0 on the interval $[t_0, t_0 + x_i^m]$ then, $k$ cannot be updated in the same interval. Thus, $x_k^m \le x_i^m$. Moreover, the latter observations imply that $i$ and $k$ are synchronized, i.e. $(\bar{x}^c(0))_k = (\bar{x}^c(0))_i$, $x_k^m = x_i^m$, $t_1 = x_i^m$ and $t_0 = t_1 + x_i^m$. Note that also, we have that for all $t$, $\bar{x}(t)_i = 1 - \bar{x}(t)_k$. We have shown that the period of any node $v$ is at most $2x_v^m$, so we deduce $p(\bar{x}) \le 2 \text{lcm}\{x_v^m : v \in \{1, \dots, n\}\}$.

At this point, we know that $i$ must have at least one neighbor that is not constant in $\bar{x}$ and that it is synchronized. Let us assume that there is a non constant neighbor $\ell$ of $i$ that satisfies $x_\ell^m > x_i^m$. On the other hand, we have that
<figure><img src="image_19.png" /><figcaption>Figure 15: Scheme of the dynamics of nodes i, k and ℓ defined in the proof of Lemma 22. The checkmarks indicate where it is feasible for ℓ to be updated and the crosses mark the intervals on which ℓ can change its state.</figcaption></figure>

ℓ is in state 1 on the interval $[0, t_1]$ (see Figure 15) because otherwise i cannot switch to state 1 at the time step $t_1$. Observe that, by hypothesis, ℓ cannot change its state on intervals of the form $[rx_i^m, (r+1)x_i^m)$ for $r \in \mathbb{N}$ even since i is in state 0 on those intervals (otherwise i cannot switch back to 1 because it would have a neighbor in 0). However, for r even, i is in state 1 on intervals of the form $[rx_i^m, (r+1)x_i^m)$. Suppose that ℓ changes its value for the first time on an interval of the form $[r^*x_i^m, (r^*+1)x_i^m)$ for some $r^* \in \mathbb{N}$ odd, i.e. $\bar{x}(s)_\ell = 0$ for some $s \in [r^*x_i^m, (r^*+1)x_i^m)$. Observe now that $\bar{x}((r^*+2)x_i^m) = 1$ since i must return to state 1 but ℓ cannot change its state in $[(r^*+1)x_i^m, (r^*+2)x_i^m)$ because i is in state 0. Then, we must have $x_\ell^m \le x_i^m$, which contradicts the hypothesis. We conclude that every non constant neighbor of i is synchronized. Repeating the same argument now for any non constant neighbor of i we have that all the nodes in the connected component containing i have local delay $x_i^m$. Iterating this same technique now for each i in the network, we deduce that $\bar{x}$ is such that $p(\bar{x}) \le 2\text{lcm}\{x_v^m : v \in \{1, \dots, n\}\}$ since locally, each connected component containing some node i is synchronized and thus, each non-constant node is switching its state every $2x_i^m$ time steps. In addition, for each node i every non-constant neighbor is in the state 0 whenever i is in the state 1. Thus, the set of nodes which are not constant for $(\bar{x}^Q, \bar{x}^c, \bar{x}^m)$ i.e. $S(\bar{x}^Q, \bar{x}^c, \bar{x}^m)$, induces a two colorable subgraph. The result holds. □

As seen above, there is a qualitative jump between local clocks and periodic update schedules for conjunctive networks in the size of dynamical cycles. However, for transient and prediction problems, even general periodic update schedules fail to produce maximal complexity (under standard complexity classes separations assumptions).

**Theorem 23.** Let $p \in \mathbb{N}$ and consider the family $\mathcal{F}_{\text{pos}}^{\text{PER},p}$ of positive conjunctive networks under periodic update schedules of period $p$. $\mathcal{F}_{\text{pos}}^{\text{PER},p}$ is neither dynamically nor computationally complex: more precisely, the transients of any network in $\mathcal{F}_{\text{pos}}^{\text{PER},p}$ with $n$ nodes are of length at most $O(n^2)$, the problem $\text{PRED}_{\mathcal{F}_{\text{pos}}^{\text{PER},p}}$ can be solved by a $\mathbf{NC}^2$ algorithm and $\text{PRED}_{\mathcal{F}_{\text{pos}}^{\text{PER},p}}$ can be solved in polynomial time.

*Proof.* Let $F \in \mathcal{F}_{\text{pos}}^{\text{PER},p}$ with $n$ nodes and consider any initial configuration $x$. By definition, the orbit of $x$ under $F^p$ is constant on the second and third component of states, and the action of $F^p$ on the first component when starting from $x$ is a particular non-symmetric conjunctive network $F_x$ that can be seen as an arbitrary Boolean matrix $M_x$. First, by [23, Theorem 3.20], the transient of the orbit of $x$ under $F_x$ is of length at most $2n^2 - 3n + 2$. We deduce that the transient of $x$ under $F$ is in $O(n^2)$.

Second, it is easy to compute $M_x$ from $F$ and $x$ in $\mathbf{NC}^1$. Moreover, matrix multiplication can be done in $\mathbf{NC}^1$.
and by fast exponentiation circuits we can compute $M_x^t$ with polynomial circuits of depth $O(\log(t) \log(n))$. With a constant computational overhead, we can therefore efficiently compute $F^t(x)_v$ and the complexity upper bounds on $\mathrm{PRED}_{\mathcal{F}^{\mathrm{PER},p}_{\mathrm{pos}}}$ and $\mathrm{PREDB}_{\mathcal{F}^{\mathrm{PER},p}_{\mathrm{pos}}}$ follow. □

**Remark 5.** We remark that even when symmetric conjunctive networks under periodic update schemes are not dynamically nor computationally complex, it has been shown that, with a different type of update schemes, it is possible to construct coherent monotone gadgets and thus, show strong universality for this latter family. Particularly, we allude to the case of firing memory update schemes, which can also be studied in the context of our asynchronous extensions framework, as same as periodic update schemes. Just as we have mentioned before, this type of update scheme introduces internal clocks in each node, which will actually depend on the dynamics of the network (contrarily to the case of local clocks, where clocks are fixed and independent from the dynamics of the network). This key aspect gives the network strong dynamical and computational capabilities which can be used to simulate monotone boolean networks. Interested reader is referred to in order [24] to see details.

## 5. Counter examples to the desymmetrization phenomena

The examples studies above all follow a striking phenomenon: a base concrete family over symmetric graphs is able to simulate its non-symmetric (directed) version when one allows sufficiently rich asynchronous updates (periodic updates are enough in all cases). One can wonder how general is the phenomenon of desymmetrization by asynchronism. In this section, we give two examples of CSAN families that have opposite behaviors when one compares their periodic update extension and their non-symmetric version with parallel update. Let us first start by an example where the non-symmetric version is strictly more powerful than the periodic update extension.

**Proposition 2.** There exists a CSAN family $\mathcal{F}$ such that none of its periodic update extension $\mathcal{F}_p$ can simulate its non-symmetric version $\overline{\mathcal{F}}$, whatever $p \in \mathbb{N}$.

*Proof.* Let $Q = \{0,1\} \times \{0,1\} \cup \{e\}$ and denote by $\pi_1$ and $\pi_2$ the projections on the first and second components respectively for states in $\{0,1\} \times \{0,1\}$. We construct a family which essentially applies a majority rule on one component of composite states, does synchronization checks using the second component, and use $e$ as an error state that spreads over the network. More precisely, consider the local map $\lambda: Q \times \mathbb{N}^Q \to Q$ that does the following at each node $v$:

* if $e$ appears in the neighborhood, then the image by $\lambda$ at $v$ is $e$;

* otherwise, let $M_1$ be the multiset of states of the $\pi_1$ components of states of neighbors and the node itself and denote by $m_1$ the state with a majority of occurrences in $M_1$ ($\pi_1$ of the state of $v$ in case of tie); then

- if all neighbors of node $v$ (including $v$) have the same $\pi_2$ component $b$, then the image by $\lambda$ at $v$ is $(m_1, 1-b)$;

- otherwise, the image by $\lambda$ at $v$ is $e$.
The CSAN family $\mathcal{F}$ we consider is that defined by this local rule $\lambda$ at each node. Consider any automata network of the periodic update extension of $\mathcal{F}$ of period $p$, and consider any limit cycle of some of its orbits. We show that this limit cycle has length at most 2. There are two cases:

* if the update scheme is not a synchronous update scheme (all nodes update exactly at the same time steps), then there must be some time step at which a node $v$ is updated but some of its neighbors $v'$ isn't. So either $v$ updates to $e$ at this time step, or $v$ updates to a composite state with a $\pi_2$ component different from the $\pi_2$ component of $v'$. In the second case the next node to update among $v$ and $v'$ will update to $e$. Finally, since $e$ appears at some node in the orbit, its means that the limit cycle is the fixed point configuration everywhere equal to $e$.

* if the update scheme is the parallel update scheme, then: either $e$ appears in the considered orbit and the limit cycle is a fixed point; or $e$ never appears, which means that the $\pi_2$ component of nodes is oscillating between 0 and 1 and the behavior in the $\pi_1$ component is that of the classical majority rule with parallel update mode, hence also of period 2.

We conclude that the family $\mathcal{F}_p$ has only limit cycles of length $\le 2$, whatever $p$. If we consider now the non-symmetric version $\overline{\mathcal{F}}$, it is straightforward to build limit cycle of length $n$ (size of the network) using synchronized $\pi_2$ components. So $\mathcal{F}_p$ cannot simulate $\overline{\mathcal{F}}$ (actually, it is not hard to show that $\overline{\mathcal{F}}$ is strongly universal since it admits coherent monotone gadgets). □

Let us now give an example of CSAN family where the opposite situation occurs: periodic extensions are stronger than the non-symmetric version.

**Proposition 3.** *There exists a CSAN family $\mathcal{F}$ such that its periodic update extension $\mathcal{F}_p$ for some $p$ cannot be simulated by its non-symmetric version $\overline{\mathcal{F}}$.*

*Proof.* Consider any CSAN family $\mathcal{F}_0$ over alphabet $Q$ than can produce orbits with limit cycles of non-constant length over symmetric networks that are bipartite: one can for instance choose $\mathcal{F}_0$ to be the family of positive conjunctive networks under periodic update schedule of period 3 (see Theorem 21). Define a new alphabet $Q' = Q \cup Q \times \{0,1\} \cup \{e\}$ where we distinguish three types of states: the error state $e$, composite states from $Q \times \{0,1\}$, and pure states from $Q$. For a non-error state, its $Q$-content is either itself (when it is pure) or the projection on its $Q$ component (when it is composite). Let's define the family $\mathcal{F}$ by the following local behavior on any graph:

* $e$ states spread over the network, i.e. any node with an incoming neighbor in state $e$ updates to state $e$;

* if a node has a pure (resp. composite) state, then all its incoming neighbors must have a composite (resp. pure) state otherwise it updates to $e$ in one step; moreover, any pure state with some incoming neighbor in a state from $Q \times \{0\}$ will also update to $e$ (so when a node in a pure state is updated, all its incoming neighbors must be in a state from $Q \times \{1\}$ to prevent it from updating to $e$);

* outside the above cases, the type of a state doesn't change and
- if it is a pure state, its $Q$-content changes according to the local rules over $Q$ of the chosen CSAN family $\mathcal{F}_0$;

- if it is a composite state, its $\{0,1\}$ component is inverted (by $b \mapsto 1-b$), and its $Q$-content is updated according to the local rules over $Q$ as above, but only when the $\{0,1\}$ component is 1, otherwise the $Q$-content is left unchanged.

Now take any connected automata network from the non-symmetric version $\overline{\mathcal{F}}$ of the family we just defined. We claim that any orbit reaches a fixed-point. First it is well-known that if the network graph is acyclic, then all orbits converge to a fixed-point. So let's consider the case where the network graph possesses a directed cycle $C$. Consider some configuration $x$, and let us show that $e$ must appear in the network at some step which implies that the orbit will reach a fixed-point. If the type of states does not alternate between pure and composite along cycle $C$, then $e$ is generated in one step. If the type of states correctly alternates in $C$ between pure and composite, then there must be a first step $t$ where some node of $C$ is in a composite state with value 0 on its $\{0,1\}$ component. Since $C$ is a cycle, this node is the incoming neighbor of some other node in a pure state. This last node will update to $e$ in this situation. This concludes the claim that any orbit reaches a fixed point in any network of $\overline{\mathcal{F}}$.

Let us now consider any bipartite symmetric network and some orbit of an automata network of family $\mathcal{F}_0$ reaching a long limit cycle. We can simulate this orbit starting from the $Q$-configuration $x$ by applying a periodic update scheme of period 2 to some automata network of family $\mathcal{F}$ on the same network as follows: by bi-partition of the network we can distribute the type of states (pure/composite) in such a way that no node has a neighbor with the same type as itself; then we update composite nodes at each step and pure nodes once every two steps (and start to update them at first step); we choose as initial configuration a configuration where the $Q$-contents correspond to $x$ and all composite node start with 1 in their $\{0,1\}$ component. This shows that the periodic update extension of period 2 of $\mathcal{F}$ cannot be simulated by its non-symmetric version $\overline{\mathcal{F}}$. $\square$

# 6. Perspectives

The main results of this paper extend previous results [24, 25, 18] on the strong interplay between symmetry of local interactions and update modes. We showed how universality can be recovered from the symmetry constraint by allowing various degrees of asynchronism. An immediate question following our work is to find a natural example of a CSAN family which is (strongly) universal under periodic update schemes, but not universal under local clocks update schemes.

Besides universality, it would be interesting to better understand in general when a symmetric family can simulate its non-symmetric version under non-parallel update modes (as it was shown in Theorem 21). Here again, we are interested in the level of asynchronism required for this simulation to hold.

Another natural research direction is to try to further extend this analysis to other update modes. As we have pointed out in the update schemes section (see Remark 2), it would be interesting to study other types of update schemes which are not captured by general periodic update schemes such as firing memory schemes [24, 22], or
845

other modes where the decision to apply an update at a node depends on its state (for instance we can interpret reaction-difussion systems [6] as threshold networks with an update mode with memory). We can consider even more general ones inspired by the most permissive semantics studied in [11]. In some cases, Definition 12 of asynchronous extension should be adapted in order to capture latter update schemes.

850

## References

[1] W. S. McCulloch, W. Pitts, A logical calculus of the ideas immanent in nervous activity, The Bulletin of Mathematical Biophysics 5 (4) (1943) 115-133. doi:10.1007/bf02478259.

[2] R. Thomas, Boolean formalization of genetic control circuits, Journal of Theoretical Biology 42 (3) (1973) 563-585. doi:10.1016/0022-5193(73)90247-6.

[3] S. Kauffman, Homeostasis and differentiation in random genetic control networks, Nature 224 (5215) (1969) 177-178. doi:10.1038/224177a0.

855

[4] M. Gadouleau, S. Riis, Memoryless computation: new results, constructions, and extensions, Theoretical Computer Science 562 (2015) 129-145.

[5] E. G. Ch., P. Montealegre, Computational complexity of threshold automata networks under different updating schemes, Theor. Comput. Sci. 559 (2014) 3-19. doi:10.1016/j.tcs.2014.09.010.

860

[6] E. Goles, M. Matamala, Reaction-diffusion automata: Three states implies universality, Theory of Computing Systems 30 (3) (1997) 223-229.

[7] A. Wu, A. Rosenfeld, Cellular graph automata. ii. graph and subgraph isomorphism, graph structure recognition, Information and Control 42 (1979) 330-353. doi:10.1016/S0019-9958(79)90296-1.

865

[8] A. Wu, A. Rosenfeld, Cellular graph automata. i. basic concepts, graph property measurement, closure properties, Information and Control 42 (3) (1979) 305-329. doi:10.1016/S0019-9958(79)90288-2.

[9] J. Demongeot, S. Sené, About block-parallel boolean networks: a position paper, Nat. Comput. 19 (1) (2020) 5-13. doi:10.1007/s11047-019-09779-x.

[10] M. Gadouleau, On the influence of the interaction graph on a finite dynamical system, Natural Computing 19 (1) (2019) 15-28. doi:10.1007/s11047-019-09732-y.

870

[11] T. Chatain, S. Haar, L. Paulevé, et al., Most permissive semantics of boolean networks, arXiv preprint arXiv:1808.10240 (2018).

[12] J. Aracena, A. Richard, L. Salinas, Fixed points in conjunctive networks and maximal independent sets in graph contractions, J. Comput. System Sci. 88 (2017) 145-163.

[13] E. Goles, M. Noual, Disjunctive networks and update schedules, Adv. Appl. Math. 48 (2012) 646-662.

875

[14] J. Aracena, E. Goles, A. Moreira, L. Salinas, On the robustness of update schedules in boolean networks, Biosystems 97 (1) (2009) 1-8. doi:10.1016/j.biosystems.2009.03.006.
[15] F. Robert, Blocs-h-matrices et convergence des methodes iteratives classiques par blocs, Linear Algebra and its Applications 2 (2) (1969) 223-265. doi:10.1016/0024-3795(69)90029-9.

880

[16] E. Goles, J. Olivos, Periodic behaviour of generalized threshold functions, Discrete Mathematics 30 (2) (1980) 187 - 189. doi:http://dx.doi.org/10.1016/0012-365X(80)90121-1.

[17] E. Goles-Chacc, F. Fogelman-Soulie, D. Pellegrin, Decreasing energy functions as a tool for studying threshold networks, Discrete Applied Mathematics 12 (3) (1985) 261-277.

[18] E. Goles, P. Montealegre, Computational complexity of threshold automata networks under different updating schemes, Theoretical Computer Science 559 (2014) 3-19.

885

[19] E. Goles, P. Montealegre, V. Salo, I. Törmä, Pspace-completeness of majority automata networks, Theor. Comput. Sci. 609 (2016) 118-128. doi:10.1016/j.tcs.2015.09.014.

[20] M. Ríos-Wilson, G. Theyssier, Intrinsic Universality in Automata Networks I: Families and Simulations, preprint available on HAL and arXiv (2023).

890

[21] M. Ríos-Wilson, G. Theyssier, Intrinsic Universality in Automata Networks II: Glueing and Gadgets, preprint available on HAL and arXiv (2023).

[22] E. Goles, F. Lobos, G. A. Ruz, S. Sené, Attractor landscapes in Boolean networks with firing memory, Natural Computing 19 (2019) 295-319.

[23] B. D. Schutter, B. D. Moor, On the sequence of consecutive powers of a matrix in a boolean algebra, SIAM Journal on Matrix Analysis and Applications 21 (1) (1999) 328-354. doi:10.1137/s0895479897326079. URL https://doi.org/10.1137%2Fs0895479897326079

895

[24] E. Goles, P. Montealegre, M. Ríos-Wilson, On the effects of firing memory in the dynamics of conjunctive networks, Discrete & Continuous Dynamical Systems - A 40 (10) (2020) 5765-5793. doi:10.3934/dcds.2020245. URL https://doi.org/10.3934/dcds.2020245

[25] E. Goles, P. Montealegre, V. Salo, I. Törmä, Pspace-completeness of majority automata networks, Theoretical Computer Science 609 (2016) 118-128.

900