B Mossé

É Remy

A combinatorial exploration of boolean dynamics generated by isolated and chorded circuits

, we consider chorded circuits, that are motifs made of an elementary positive or negative circuit with a chord, possibly a self-loop. We provide detailed descriptions of the boolean dynamics of chorded circuits versus isolated circuits, under the synchronous and asynchronous updating schemes within the logical formalism. To this end, we address the description of the trajectories in the dynamics of isolated circuits with coding techniques and adapt them for chorded circuits. The use of the logical modeling gives access to mathematical tools (group actions, analysis of recurrent sequences, coding of trajectories, specific abacus...) allowing complete analytical analysis of basic yet important motifs. In particular, we show that whatever the chosen updating rule, the dynamics depends on a small number of parameters.

.

The proofs and results presented in this paper go deeply into mathematical details, with combinatorics and coding arguments and tools developed in a series of propositions and remarks. Such a precise description allows a very fine understanding of the dynamics of the model seen as a discrete events system, and how it functions. Anyway, the reader may choose the level of reading; it is possible to capture the main results stated in the theorems without going into all details.

Introduction

Motivation Biological processes are complex systems, involving a large number of components in strong non-linear interactions. Dynamical behaviors of cells may be viewed as emergent properties of the underlying biological interaction networks. Hence, systems biology approaches aim at studying biological interaction networks to get insight of the cell functioning and a better understanding of biological processes. Regulatory networks are usually represented in terms of signed, directed graphs, whose nodes represent molecular components, and edges interactions between them (typically activations or inhibitions). These static graphs, called regulatory graphs (RG), are endowed with a set of mathematical parameters coding for the dynamics, and defining a finite dynamical system (FDS) associated to a transformation of a state space. Clearly, this FDS contains the structure of the underlying interaction network (i.e. the RG), namely the edges between components, their direction and sign (+ for activation, -for inhibition). Different FDS may correspond to the same RG, but the topological structure of the RG constraints the possible dynamical behaviors of the system, particularly in term of asymptotical behavior (e.g. an acyclic graph can only generate a unique stable state [Robert, 1986, Shih and[START_REF] Shih | [END_REF]). One of the challenging task is to emphasize and describe these links between properties of the dynamics (FDS) and properties of the topology of the RG. A way to address this question is to focus on specific topological motifs (i.e. small subnetworks) present in the graph, and their role in the dynamics. Famous examples are the regulatory circuits, also called feedback loops or feedback circuits, known to play significant dynamical roles [Thomas and D'Ari, 1990]. In particular, positive regulatory circuits (involving an even number of negative interactions) have been associated with multistability, and more generally with the occurrence of multiple attractors, which may account for biological differentiation phenomena. On the other hand, negative regulatory circuits (involving an odd number of negative interactions) have been associated with sustained periodic behaviours (e.g. homeostasis) [Thomas, 1981]. Hence, clearly, the complexity of the dynamics comes from the circuits. By the way, most important known biological motifs contain circuits [Alon, 2007].

In this context, it is relevant to have a very precise knowledge of the behaviour of these motifs. This paper presents an exhaustive analysis providing precise mathematical description of dynamics of circuits, compared with those of chorded circuits. These motifs, in which a single edge is added to a circuit (chord, or short-cut), are largely present in real biological networks. Such comparison allows to understand the impact of edgetic alterations in the RG. Indeed the outcome of diseases may be the consequence of network alterations [START_REF] Baëza | Inhibitory activities of short linear motifs underlie Hox interactome specificity in vivo[END_REF].

Hence, to each motif is associated a proper dynamics. When embedded in a RG, a motif may be perturbated by the influence of incoming regulations: it is said functional whenever its expected dynamics is conserved. This functionality is strongly context-dependant. An in-depth knowledge of motifs contributes to the analysis of their functionality [Remy andRuet, 2006, Comet et al., 2013].

Basic glossary Classical terms of graph theory can be found in [START_REF]Digraphs, Theory, Algorithms, Applications[END_REF]. Moreover, we will use in this manuscript the following terminology:

• Isolated (elementary) circuit: a connected directed graph with every vertex of in-degree and out-degree equal to 1 (see Figure 1, left);

• Circuit: a subgraph of a regulatory graph amounting to an isolated circuit;

• Chorded circuit: circuit with a chord, possibly a self-loop (see Figure 1, right).

Notations and definitions

Notations 1.

• For a ∈ {0, 1}, a = 1 -a;

• For a ∈ {0, 1} and ε ∈ {±1},

a ε = { a if ε = +1, a if ε = -1.
• For any n ≥ 1 and x ∈ {0, 1} n , x = (x 1 , . . . , x n ) and x j = (x 1 , . . . , x j-1 , x j , x j+1 , . . . , x n ).

Definitions 1. A state is an element x = (x 1 , . . . , x n ) of X = {0, 1} n . For any transformation T : X → X, and x ∈ X, we will consider the updating set U pd T (x) = {i ∈ {1, . . . n} ; (T (x)) i ̸ = x i }.

A state x is stable if U pd T (x) = ∅. Hence, a stable state is a state invariant under the action of T .

Remark 1. The stable states are fixed points of the transformation T . The unstable fixed points are not captured within the logical modelling (cf [START_REF] Snoussi | Logical identification of all steady states: the concept of feedback loop characteristic states[END_REF]).

In this work, we will be concerned with two types of regulatory graphs, whose vertices g 1 , g 2 , . . . , g n are called components, endowed with a transformation of X (see Figure 1):

• Isolated circuits C n (ε 1 , . . . , ε n ), with n ≥ 2 and for i ∈ {1, . . . , n}, ε i ∈ {±1}. The sign of C n (ε 1 , . . . , ε n ) is given by the product ς = ∏ n i=1 ε i . The associated transformation is S, defined by: S(x 1 , x 2 , . . . , x n ) = (x εn n , x ε 1 1 , . . . , x

ε n-1
n-1 ).

• Chorded circuits CC ⊥ n,q (ε 1 , . . . , ε n ; ε (s)

n-q ), with n -q ≥ 1, q ≥ 1, ⊥: {0, 1} × {0, 1} → {0, 1}, and for i ∈ {1, . . . n}, ε i ∈ {±1}, ε (s) n-q ∈ {±1}.

The graph CC ⊥ n,q (ε 1 , . . . , ε n ; ε (s) n-q ) contains two circuits, a longer one

C n (ε 1 , . . . , ε n ) with sign ς = ∏ n i=1 ε i , and a smaller one C n-q (ε 1 , . . . , ε n-q-1 , ε (s) n-q ) with sign ς (s) = ε (s) n-q ∏ n-q-1 i=1 ε i .
The chorded circuit is said coherent if the signs of these two embedded circuits are identical (ς ς (s) = +1); otherwise, it is said incoherent (ς ς (s) = -1).

The associated transformation S ⊥ is defined by:

S ⊥ (x 1 , . . . , x n-q , . . . , x n ) = (x εn n ⊥ x ε (s) n-q n-q , x ε 1 1 , . . . , x ε n-1 n-1 ) .
The considered chorded circuits are related to any given boolean function ⊥, but in this work we deal with the cases ⊥∈ {and, or, xor} = {∧, ∨, ⊕}. Furthermore, the case n -q = 1 corresponds to the situation where the chorded circuit is realised by a self-loop in the regulatory graph, also called self-regulation of g 1 . All these instances are meaningful in biology.

For T = S and T = S ⊥ , the choice of updating rules determines the definition of dynamics. We consider here two updating rules:

• the synchronous dynamics, with a simultaneous change of all the coordinates of the state x specified by U pd T (x): any state has exactly one successor (possibly itself), and the dynamics is deterministic;

• the asynchronous dynamics, with at most one coordinate change at a time: a state x has as many successors as the cardinal of U pd T (x), and so the dynamics is non-deterministic.

g 1 g 2 g 3 . . . g n-1 g n ε 1 ε 2 εn g 1 g 2 g 3 . g n-q . g n-1 g n ε 1 ε (s) n-q ε 2 ε n-q εn Figure 1: The two regulatory graphs considered: isolated circuit C n (ε 1 , . . . , ε n ) (left); chorded circuit CC ⊥ n,q (ε 1 , . . . , ε n ; ε (s) n-q ) (right).
We represent the dynamics by a directed graph, called the state transition graph (STG); the set of nodes of the STG is X (the set of states), and each edge links two consecutive states in the dynamics. In the synchronous case, the STG is also called the synchronous graph, which is nothing else but the graph of the transformation. The synchronous graph of the transformation S (resp. S ⊥ ) is denoted by ξ (resp. ξ ⊥ ). In the asynchronous case, the STG is also called the asynchronous graph; it will be denoted by ξ a for the transformation S, and ξ ⊥ a for S ⊥ .

Remark 2. We start giving a priori signs to the interactions. In case of isolated circuits, this univocally identifies the dynamics. However, in the presence of multiregulated components, the dynamics may be more complex, and signs depending on the context can be infered from the logical rules. This happens in xor situation, where these local signs may differ in some contexts from the signs defined a priori.

Sections summary

In Section 3, we give a complete description of synchronous STGs of isolated cicuits and chorded circuits, and we compare them.

The synchronous STG of an isolated circuit is studied in Section 3.1. It encompasses vertexdisjoint cycles involving states with the same number of coordinates called for change, i.e. the same number of "updating calls". The STG can be hierarchically organised in levels corresponding to this number, which is even in the case of positive circuits, and odd in the case of negative circuits. The global topology of the STG (number of cycles by level and their lengths) depends only on the number of components and the sign of the circuit.

The synchronous STG of a chorded circuit is studied in Section 3.2. Comparing the synchronous STG of a chorded circuit with the one of its long circuit reveals that only a subset of states, called short-cut sensitive states (scs-states), behaves differently.

The dynamics obtained with or and and rules are symmetrical: ξ ∧ can be obtained from ξ ∨ by switching 0 and 1 for all component values. The topology of the STG depends on the number of components, the place of the shortcut, the signs of the two intertwinted circuits. In contrast, the topology of the STG obtained with the xor rule depends only on the number of components and the place of the shortcut.

In case of or and and logical rules, the synchronous STG contains terminal cycles: -If the long circuit is positive, these cycles are found in the synchronous STG of the long circuit. If the chorded circuit is coherent (positive small circuit), there are two stable states; if it is incoherent (negative small circuit), there is only one stable state.

-If the long circuit is negative, the terminal cycles differ from those obtained for the long circuit. If the chorded circuit is incoherent (positive small circuit), there is only one stable state; if it is coherent (negative small circuit), there is no stable state.

Accordingly, a coherent chorded circuit and its corresponding long circuit have the same number of stable states.

In the case of the xor rule, the synchronous STG is constituted of vertex-disjoint cycles. It contains only one stable state, and cycles with pseudo-random sequence of states, whatever the signs of the circuits.

Section 4 is analogous to Section 3 in the asynchronous case. The asynchronous STG of an isolated circuit, studied in Section 4.1, is a connected graph. Connections between vertex-disjoint cycles of a same level (defined in Section 3.1) create strongly connected components, gathering states with the same number of successors. Only the two extremal levels may be constitued of two disconnected states (cf Figure 6). The presence of two stable states (and no cyclic attractor) caracterizes positive isolated circuits, and the presence of a cyclic attractor (and no stable state), negative ones.

The asynchronous STG of a chorded circuit is studied in Section 4.2. As obtained in Section 3, the topology of the STG, and thus the dynamical properties, depend only on the sign of the two circuits in case of or and and rules. The topology of the STG and the dynamics obtained with the xor rule depends only on the number of components involved.

In case of or and and rules, the STG is obtained from that of the long circuit by changing the direction of edges between pairs of sensitive states, if the small circuit is not a self-loop. Otherwise, edges are suppressed or created. A coherent chorded circuit and its corresponding long circuit have the same number and type of attractors, and in particular the same number of stable states. When the chorded circuit is incoherent (the two circuits of different signs), there is a unique attractor (a stable state).

The introduction of a short-cut skews the symmetrical dynamics of isolated . For example, in case where both long and small circuits are positive, the basin of attraction of one of the stable states is increased at the expense of the other one.

In case of xor logical rule, the asynchronous STG of a chorded circuit encompasses a unique stable state as sole attractor.

Figure 2 summarizes the results. Remark 3. For the sake of clarity, we use the term "circuit" when we consider the regulatory graph, and "cycle" when we consider the STG, even if they are identical in terms of graph theory.

Synchronous dynamics

In this section we present a complete description of synchronous graphs ξ and ξ ⊥ , and compare them. From now on, the indices are considered modulo n, in other words they are elements of Z/n Z (classes of integers modulo n). Moreover σ stands for the increment of 1 on Z/n Z.

Proposition 1. The synchronous application S is a one-to-one transformation (or permutation) of X = {0, 1} n , and the synchronous graph ξ is composed of disconnected cycles.

Proof. The application S maps each state x = (x 1 , . . . , x n ) ∈ X to a unique state y = Sx, where (Sx) i+1 = (x i ) ε i . Therefore S is a permutation of the finite set X, its inverse application being given by (S -1 y) i = (y i+1 ) ε i . Consequently, its graph ξ is composed of disconnected cycles.

The following properties concerning the sets U pd S (x) will lead to a complete description of graph ξ.

Proposition 2. Given a state x, the set U pd S (Sx) is obtained from U pd S (x) by the action of σ :

U pd S (Sx) = σ(U pd S (x)).
Proof. By the definition of U pd S , the index j + 1 is an element of U pd S (Sx) as soon as (S 2 x) j+1 ̸ = (Sx) j+1 . This is equivalent to

x ε j-1 ε j j-1 ̸ = x ε j j , i.e. x ε j-1 j-1 ̸ = x j . Thus, the assertion j + 1 ∈ U pd S (Sx) is equivalent to j ∈ U pd S (x).
Proposition 3. Let P be a subset of {1, . . . , n} with k elements.

1. In the case of positive circuit, if k is even, there exists exactly two states x and y in X such that U pd S (x) = U pd S (y) = P , which are mirroring each other (y = x). In particular, there exists two stable states (case k = 0). If k is odd, there is no state x such that U pd S (x) = P .

2. In the case of negative circuit, if k is odd, there exists exactly two states x and y in X such that U pd S (x) = U pd S (y) = P , which are mirroring each other (y = x). If k is even, there is no state x such that U pd S (x) = P . In particular, there is no stable state.

Proof. Let P be a subset of {1, . . . , n} with k elements, and let us denote η i = -ε i if (i + 1) ∈ P , and η i = ε i otherwise.

Then, as soon as its first coordinate x 1 is given, a state x satisfies U pd S (x) = P if and only if

x 2 = x η 1 1 , x 3 = x η 2 2 = x η 1 η 2 1 , . . . , x n = x η n-1 n-1 = x η 1 η 2 ...η n-1 1
, with the additional condition

x 1 = x η 1 ...ηn 1 , i.e. ∏ n i=1 η i = +1. • If k is even, then ∏ n i=1 ε i =
∏ n i=1 η i = +1 requires a positive circuit; two mirroring states x and y are then satisfying U pd S (x) = U pd S (y) = P , one with x 1 = 0 and the other with x 1 = 1. In particular, there are two stable states if the circuit is positive.

• If k is odd, then ∏ n i=1 ε i = - ∏ n i=1 η i = -1 requires a negative circuit;
as in the previous case, two mirroring states are then associated to P . In particular, there is no stable state if the circuit is negative.

Proof of Lemma 1 relies on the theory of group actions (see for example [Lang, 1997] -page 25).

Lemma 1. Let P be a subset of {1, . . . , n} with k elements, m the smallest positive integer such that σ m P = P , and δ = k m n ; then δ is an integer. Proof. Let us identify {1, . . . , n} and Z/n Z. The group Z/n Z acts on subsets P of Z/n Z with k elements by translation: r.P = σ r P . The isotropy group of P for this action, Stab(P ) = {r ∈ Z/n Z; σ r P = P }, is a subgroup of Z/n Z with d = n m elements. Moreover, the equality σ m P = P forces P to be union of classes of Z/n Z modulo Stab(P ), which implies that d divides k.

Proposition 4. Let P be a subset of {1, . . . , n} with k elements, m the smallest positive integer such that σ m P = P , and δ = k m n . 1. If the circuit is positive and k is even, the number of states x such that U pd S (x) = σ r P , for some natural integer r, is equal to 2 m. These states are spread, in the synchronous graph ξ, either in 2 cycles of length m if δ is even, or in one cycle of length 2 m if δ is odd.

2. If the circuit is negative and k is odd, the number of states x such that U pd S (x) = σ r P , for some natural integer r, is equal to 2 m. These states are spread, in the synchronous graph ξ, in one cycle of length 2 m.

Proof. We use notation of proofs above, and we suppose that k is even if the circuit is positive, and odd otherwise. By previous properties, for a fixed natural integer r, there are two mirroring states x and y satisfying U pd S (x) = U pd S (y) = σ r P . So, there exist 2m states x such that U pd S (x) = σ r P for some natural integer r. These 2m states are spread either in one cycle, or in two cycles having same length, depending on whether S m x is equal to x or its mirror. To determine in which situation we are, it is sufficient to compare (S m x) m+1 and x m+1 . But we have

(S m x) m+1 = x ε (m+1)-1 ...ε (m+1)-m (m+1)-m = x ε 1 ...εm 1 and x m+1 = x η 1 ...ηm 1 , so that (S m x) m+1 = x m+1 if and only if ε 1 . . . ε m = η 1 . . . η m , i.e. if and only if δ = k d is even.
Thus, Proposition 3 and 4 allow to give a description of the structure of the synchronous dynamics of the isolated circuits as follows.

Theorem 1. Let ς be the sign of C n (ε 1 , . . . , ε n ).
1. If ς = +1, the synchronous graph ξ involves, for each even integer k ≤ n, self mirroring cycles and pairs of mirroring cycles regrouping all the states with k updating orders. In particular, ξ involves two mirroring stable states.

2. If ς = -1, the synchronous graph ξ involves, for each odd integer k ≤ n, self mirroring cycles and pairs of mirroring cycles regrouping all the states with k updating orders. In particular, ξ involves no stable state.

Remark 4. This structure leads naturally to gather states x for which U pd S (x) has k elements. We call "states of the kth level" the states x such that #U pd S (x) = k (see section 4.1 and particularly Theorem 8).

We now focus on iterates of a given state x under S. As seen previously, the sequence (S i x) i≥0 is periodic with shortest period m or 2m, depending on the parity of δ. Remark that this period is dependant on x. Proposition 5. Let x be a state.

1. If the circuit is positive, we have S n x = x, and the sequence (S i x) i≥0 is periodic with period n.

2. If the circuit is negative, we have S n x = x, and the sequence (S i x) i≥0 is periodic with period 2n.

Proof. This is the immediate consequence of the equality (Sx

) i+1 = (x i ) ε i .
Finally, we give a specific representation of the sequence (S i x) i≥0 of iterates of x, helpful to study the case of chorded-circuits (section 3.2). These iterates are laid out in a rectangular array with n columns and an infinite number of lines (see Figure 3, left). Remark that the diagonals form a periodic sequence (δ i ) i∈N taking values in a set of two elements, [0] = 00

ε 1 0 ε 1 ε 2 . . . 0 ε 1 ...ε n-1 and its mirror [1] = 11 ε 1 1 ε 1 ε 2 . . . 1 ε 1 ...ε n-1 . We extend the sequence (δ i ) i∈N on {-1, . . . , -(n -1)}, so that δ i = [x ε 1 ...ε -i -i+1 ].
The following Proposition 6 is obvious thanks to Proposition 5, and has an interesting direct consequence on the dynamics of C n (ε 1 , . . . , ε n ) (see Theorem 2 in synchronous case, and Theorem 7 in asynchronous case). Proposition 6. Let ς denote the sign of C n (ε 1 , . . . , ε n ). Given a state x and i ≥ 1 -n, let u i be the element of {0, 1} such that δ i = [u i ], so that u i = (S i (x)) 1 for i ≥ 0. The sequence (u i ) i≥1-n is periodic and follows the recurrence relation

u i = u ς i-n , f or i ≥ 1.
Theorem 2 is a corollary of Proposition 4. The proof presented uses techniques that will be further adapted for the study of chorded circuits (see Theorem 3).

Theorem 2. The topology of ξ depends only on n and the sign ς of C n (ε 1 , . . . , ε n ): the number of cycles of ξ and the lengths of these cycles depend only on these values.

Proof. Given initial conditions for the sequence (u i ) i≥1-n introduced in Proposition 6, that is given (u 1-n , . . . , u 0 ), there is a relationship between the iterates of the state

x = (u 0 , u ε 1 -1 , u ε 1 ε 2 -2 , . . . , u ε 1 ...ε n-1 1-n ) under S and (u i ) i≥1-n , given by the equalities S i (x) = (u i , u ε 1 i-1 , u ε 1 ε 2 i-2 , . . . , u ε 1 ...ε n-1 i+1-n ) for i ≥ 0.
Therefore, varying the initial conditions provides sequences (u i ) i≥1-n which fully describe the topology of ξ, in which the cycles are linked to their periodic behaviour.

Synchronous dynamics of the chorded circuit CC

⊥ n,q (ε 1 , . . . , ε n ; ε (s) n-q )
The addition of a chord in the circuit creates a short-cut. We compare the dynamics of chorded circuits

CC ⊥ n,q (ε 1 , . . . , ε n ; ε (s)
n-q ) with those of circuits C n (ε 1 , . . . , ε n ) to emphasize the effects of the short-cut. For this we should naturally consider the states x for which S ⊥ (x) ̸ = S(x).

Definition 1. A state x is a short-cut sensitive state (or a scs-state) if S ⊥ (x) ̸ = S(x), i .e. if x εn n ⊥ x ε (s) n-q n-q ̸ = x εn n .
The synchronous graph ξ ⊥ is obtained from ξ by diverting for each scs-states x the edge from x to S(x) toward S(x)

1 ; this allows to describe the topology of ξ ⊥ from the one of ξ.

In the same way as in subsection 3.1, we represent the sequence (S ⊥i (x)) i≥0 in an array with n columns and an infinite number of lines (see Figure 3, center and right). The diagonals form a sequence (δ i ) i∈N taking values in the set of two elements, [0] = 00

ε 1 0 ε 1 ε 2 . . . 0 ε 1 ...ε n-1 and its mirror [1] = 11 ε 1 1 ε 1 ε 2 . . . 1 ε 1 ...ε n-1 . We can extend the sequence (δ i ) i∈N on {-1, . . . , -(n -1)}, so that δ i = [x ε 1 ...ε -i -i+1
]. This representation is convenient to prove the following result, providing a key ingredient for the study of attractors in the synchronous dynamics.

Proposition 7. Let ς denote the sign of C n (ε 1 , . . . , ε n ), and ς (s) the sign of C n-q (ε 1 , . . . , ε n-q-1 , ε (s) n-q ). Given a state x, let u i be the element of {0, 1} such that δ i = [u i ], for i ≥ 1-n, so that u i = (S ⊥i (x)) 1 for i ≥ 0. The sequence (u i ) i≥1-n follows the recurrence relation u i = u ς i-n ⊥ u ς (s) i-n+q , f or i ≥ 1.
Moreover, the sequence (u i ) i≥1-n is ultimately periodic.

Proof. For i ≥ 1, we set up the relation

u i = u ς i-n ⊥ u ς (s) i-n+q from the fact that (S ⊥i (x)) 1 = (S ⊥(i-1) (x)) εn n ⊥ (S ⊥(i-1) (x)) ε (s) n-q
n-q , and that (S ⊥(i-1) (x)) n is the component of δ i-n of rank n, and (S ⊥(i-1) (x)) n-q the component of δ i-(n-q) of rank n -q. The fact that (u i ) i≥1-n is ultimately periodic is an immediate consequence of the fact that {0, 1} n is a finite set.

Theorem 3. The topology of ξ ⊥ depends only on n, q and the signs ς of C n (ε 1 , . . . , ε n ) and ς (s) of C n-q (ε 1 , . . . , ε n-q-1 , ε (s) n-q ); in particular the number and the nature of attractors of the synchronous dynamics of CC ⊥ n,q (ε 1 , . . . , ε n ; ε (s) n-q ) depend only on these values.

Proof. Given initial conditions for the sequence (u i ) i≥1-n introduced in Proposition 7, that is given (u 1-n , . . . , u 0 ), there is a relationship between the iterates of the state x = (u 0 , u

ε 1 -1 , u ε 1 ε 2 -2 , . . . , u ε 1 ...ε n-1 1-n ) under S ⊥ and (u i ) i≥1-n , given by the equalities S ⊥i (x) = (u i , u ε 1 i-1 , u ε 1 ε 2 i-2 , . . . , u ε 1 ...ε n-1 i+1-n ) for i ≥ 0.
Therefore, varying the initial conditions provides sequences (u i ) i≥1-n which fully describe the topology of ξ ⊥ . In particular, the attractors of the dynamics are linked to the ultimately periodic behavior of this sequences.

Remark 5. In addition to the equalities

S ⊥i (x) = (u i , u ε 1 i-1 , u ε 1 ε 2 i-2 , . . . , u ε 1 ...ε n-1 i+1-n ) used in the previous proof, it must be noted that for i ≥ 1 the state S ⊥i (x) is a scs-state if and only if u i ̸ = u ς i-n .
Finally, the following proposition is obvious, but should be pointed out and will be completed in the cases ⊥∈ {and, or, xor} in next subsections.

Proposition 8. The cycles of the synchronous dynamics of

C n (ε 1 , . . . , ε n ) not including any scs- state of CC ⊥ n,q (ε 1 , . . . , ε n ; ε (s) n-q ) are attractors of the synchronous dynamics of CC ⊥ n,q (ε 1 , . . . , ε n ; ε (s) n-q ).

Synchronous dynamics of the chorded circuits and and or

The following property shows that the dynamics of S ∨ can be immediately deduced from the dynamics of S ∧ . Thus, without loss of generality, we only consider the case S ∧ .

Proposition 9. The dynamics of S ∨ is deduced from the dynamics of S ∧ by mirroring.

Proof. Let us denote by mir the transformation X → X which associates x to x. From the equality a ∨ b = ā ∧ b, it follows that S ∨ = mir • S ∧ • mir, and consequently, for k ≥ 1, (S ∨ ) k = mir • (S ∧ ) k • mir. This proves the property.

In the following, we compare the dynamics of CC ∧ n,q to the one of C n .

In case of CC ∧ n,q , the scs-states x are those for which

x εn n ∧ x ε (s) n-q n-q ̸ = x εn n , in other words (x n , x n-q ) = (1 εn , 0 ε (s)
n-q ). Consequently, the synchronous graph ξ ∧ is obtained from ξ by diverting for each scsstates x the edge from x to S(x) toward S(x)

1 , so that the first coordinate of S ∧ (x) is equal to 0.

In addition, it is interesting, to specify the topology of ξ ∧ , to determine the antecedents x of a state y ∈ X by the transformation S ∧ , namely the states x such that S ∧ (x) = y.

Proposition 10. Let y be an element of X.

• if y 1 = 1 and y n-q+1 = 0 ε n-q ε (s)
n-q , then y has no antecedent by S ∧ ,

• if y 1 = 0 and y n-q+1 = 0 ε n-q ε (s) n-q , then y has 2 antecedents, the state x such that S(x) = y, and the scs-state x n ,

• otherwise y has 1 antecedent, the state x such that S(x) = y.

Proof. If x verifies S ∧ (x) = y, i .e. (x εn n ∧ x ε (s) n-q n-q , x ε 1 1 , . . . , x ε n-1
n-1 ) = (y 1 , y 2 , . . . , y n-q , . . . , y n ), then for i = 1, . . . , n -1 the components x i are univocally determined by the equality

x i = y ε i i+1 , but the last component x n satisfies the constraint x εn n ∧ x ε (s) n-q n-q = x εn n ∧ y ε n-q ε (s) n-q n-q+1 = y 1 . Therefore,if y 1 = 1 and y ε n-q ε (s) n-q n-q+1
= 0, then y has no antecedent by S ∧ ; if y 1 = 0 and y

ε n-q ε (s) n-q n-q+1
= 0, then y has 2 antecedents, the unique state x such that S(x) = y, and x n ; otherwise, y has 1 antecedent, the unique state x such that S(x) = y.

We are interested in the sequence (S ∧i x) i≥0 , in order to determine the attractors of the synchronous graph ξ ∧ . In the notation of Proposition 7, the sequence (u i ) i≥1-n associated to x is given by u

i = u ς i-n ∧ u ς (s) i-n+q , for i ≥ 1.
For the purpose of next result, we recall that the 2-adic valuation v 2 (m) of a non-zero integer m is the highest exponent α such that 2 α divides m. Theorem 4. Let ς be the sign of C n (ε 1 , . . . , ε n ), and ς (s) the sign of

C n-q (ε 1 , . . . , ε n-q-1 , ε (s) n-q ). 1. If ς = +1, the synchronous dynamics of the chorded circuit CC ∧ n,q (ε 1 , . . . , ε n ; ε (s)
n-q ) involves two stable states if ς (s) = +1, and one stable state if ς (s) = -1. Moreover, the attractors of this dynamics are the cycles of the synchronous graph

ξ of C n (ε 1 , . . . , ε n ) not including any scs-state of CC ∧ n,q (ε 1 , . . . , ε n ; ε (s) n-q ).
2. If ς = -1, this dynamics involves one stable scs-state if ς (s) = +1, and no stable state if ς (s) = -1. Moreover:

• In the case ς (s) = +1, none of the attractors is a cycle of the synchronous graph ξ if and only if v 2 (q) ̸ = v 2 (n).

• In the case ς (s) = -1, none of the attractors is a cycle of the synchronous graph ξ if and only if v 2 (q) ≤ v 2 (n).

Proof. We have already noted that the cycles of ξ without any scs-state are attractors of the synchronous dynamics of CC ∧ n,q (ε 1 , . . . , ε n ; ε (s)

n-q ) (see Proposition 8). Moreover, Theorem 3 enables to restrict the study of attractors to four "generic" examples, namely CC ∧ n,q (+1, . . . , +1, ±1; ±1).

1. If ς = +1, let x be an element of X, and (u i ) i≥1-n the sequence associated to x as above. Then the n-tuple (u j+n , u j+n+1 , . . . , u j+2n-1 ) is obtained from (u j , u j+1 , . . . , u j+n-1 ) replacing by 0 the components equal to 1 related to scs-states of the sequence (S ∧i x) i≥0 (see Remark 5). Thus the number of 0 in (u j+kn , u j+kn+1 , . . . , u j+(k+1)n-1 ) increases with k, and becomes constant for k great enough. From then onwards, the sequence (u i ) i is periodic with period n, so that (S ∧i x) i no longer contains scs-states, and the conclusion follows.

To study the number of stable states, we assume that

ε 1 = • • • = ε n = +1.
Based on the foregoing, these states are among the stable states of C n (+1, . . . , +1), that is (0, . . . , 0) and (1, . . . , 1). It is then easy to verificate that either ε (s)

n-q = +1 and both are stable states of CC ∧ n,q (+1, . . . , +1; ε

(s) n-q ), or ε (s)
n-q = -1 and only (0, . . . , 0) is suitable.

2. If ς = -1, it is easily seen that concerning CC ∧ n,q (+1, . . . , +1, -1; +1) the scs-state (0, . . . , 0) is the only stable state, and that there is no stable state for CC ∧ n,q (+1, . . . , +1, -1; -1).

• If ς (s) = +1, consider an element x of X, and (u i ) i≥1-n the associated sequence, which satisfies u i = u i-n ∧ u i-(n-q) . Using similar arguments as those given in the case ς = +1 and ς (s) = -1, the (n-q)-tuple (u j+(n-q) , u j+(n-q)+1 , . . . , u j+2(n-q)-1 ) is obtained from (u j , u j+1 , . . . , u j+(n-q)-1 ) replacing by 0 the components equal to 1 related to terms of (u i ) i such that u i = u -1 i-n ∧ u i-(n-q) = 0 and u i-(n-q) = 1. Thus the number of 0 increases with k in (u j+k(n-q) , u j+k(n-q)+1 , . . . , u j+(k+1)(n-q)-1 ), and becomes constant for k great enough. From then onwards, the sequence (u i ) i is periodic with period (n-q). We suppose now that the iterates S ∧i (x) are for i great enough nodes of a cycle of ξ, that is u i+n = u i , according to Remark 5. This condition leads to the following implications: for i great enough, u i = 0 implies u i+q = 1, and, shifting right by n indices, u i = 1 implies u i+q = 0. Suppose that v 2 (q) > v 2 (n); then there exists a value of k such that (2k + 1)q is of the form 2hn, in contradiction with u i+(2k+1)q = u i = u i+2hn for i great enough: none of the attractors is a cycle of ξ. Suppose that v 2 (q) < v 2 (n); then v 2 (n -q) = v 2 (q) < v 2 (n), and there exists a value of k such that k(n -q) is of the form (2h + 1)n, in contradiction with u i+k(n-q) = u i = u i+(2h+1)n for i great enough: none of the attractors is a cycle of ξ. Lastly, suppose that v 2 (q) = v 2 (n) = α; then let (u i ) i≥1-n be a sequence of zeros and ones such that u i+2 α = u i , for i ≥ 2 α + 1 -n. It can then be easily seen that this sequence is associated to a state, node of an attractor which is a cycle of ξ.

• If ς (s) = -1, similarly, the iterates S ∧i (x) are nodes of a cycle of ξ if and only if u i+n = u i for i great enough, which gives this time that u i = 0 implies u i+q = 0, and thus u i+kq = 0 for k ≥ 0; shifting right by n indices shows that u i = 1 implies u i+kq = 1 for k ≥ 0. But then, if v 2 (q) ≤ v 2 (n), there exists a value of k such that kq is of the form (2h + 1)n, in contradiction with u i+kq = u i = u i+(2h+1)n for i great enough: none of the attractors is a cycle of ξ. Now, suppose that v 2 (q) > v 2 (n), and remark that if kq is of the form r + (2h + 1)n, and k ′ q of the form r ′ + 2h ′ n, with 0 ≤ r, r ′ < n, then r = r ′ gives (k -k ′ )q = (2(h -h ′ ) + 1)n, which contradicts the supposition that v 2 (q) > v 2 (n). Therefore kq and k ′ q have different remainders modulo n, which allows to construct states which iterates under S ∧ are nodes of a cycle of ξ, and completes the proof.

Remark 6.

1. In the case ς = ς (s) = +1, it is easy to give a more detailed description of the attractors. Indeed, using the generic example CC ∧ n,q (+1, . . . , +1; +1), the states contained in attractors are the states x = (x 1 , . . . , x n ) such that x k = 0 implies x k+q = 0, considering the indices modulo n. Given the fact that multiples of q take n gcd(n,q) values modulo n, if moreover n and q are relatively prime, then the two stable states are the only attractors of the synchronous dynamics of CC ∧ n,q (ε 1 , . . . , ε n ; ε (s) n-q ); this is in particular the case when the short-cut is a self-activation of g 1 .

In the case ς = +1 and ς (s) = -1, we can consider the generic example CC ∧ n,q (+1, . . . , +1; -1), for which the states contained in attractors are the states x = (x 1 , . . . , x n ) such that x k = 1 implies x k+q = 0, considering the indices modulo n. This implies for instance that the stable state is never the only attractor of the synchronous dynamics of CC ∧ n,q (ε 1 , . . . , ε n ; ε

(s) n-q ).
2. If ς = -1, the synchronous dynamics is more complicated, involving for the most part cycles that were not present in the case of an isolated circuit.

The case ς = -1 and ς (s) = +1 should be brought closer to the case ς = +1 and ς

(s) = -1, switching roles of C n (ε 1 , . . . , ε n ) and C n-q (ε 1 , . . . , ε n-q-1 , ε (s)
n-q ), as it is done in the proof of theorem 4. Remark 7. In cases or and and, a coherent chorded circuit have the same number of stable states than its corresponding long isolated circuit. An incoherent chorded circuit has only one stable state.

Figure 4 provides illustrations of these results in the situation n = 4, and q = 1 in cases (II) and (III), q = 3 in case (IV).

Synchronous dynamics of the chorded circuit xor

First of all, the boolean function ⊕ is identified with the addition modulo 2 on the finite field with two elements F 2 = {0, 1}.

We compare the synchronous dynamics of CC ⊕ n,q to the one of C n .

In case of CC ⊕ n,q , the scs-states x are those for which x εn n ⊕x ε (s) n-q n-q ̸ = x εn n , in other words x n-q = 1 ε (s) n-q . Consequently, the synchronous graph ξ ⊕ is obtained from ξ by diverting for each scs-state x the edge from x to S(x) toward S(x)

1 . The difference with the ∧ and ∨ cases is that the first coordinate of S ⊕ (x) can take any value (0 or 1).

Proposition 11. The transformation S ⊕ is a one-to-one transformation of X, and the synchronous graph ξ ⊕ is composed of disconnected cycles.

Proof.

If x verifies S ⊕ (x) = y, i .e. (x εn n ⊕ x ε (s) n-q n-q , x ε 1 1 , . . . , x ε n-1
n-1 ) = (y 1 , y 2 , . . . , y n-q , . . . , y n ), then for i = 1, . . . , n -1 the components x i are univocally determined by the equality

x i = y ε i i+1 . The last component x n satisfies x εn n ⊕ x ε (s) n-q n-q = x εn n ⊕ y ε n-q ε (s) n-q n-q+1
= y 1 . This gives x n = (y 1 ⊕ y

ε n-q ε (s) n-q n-q+1
) εn , so that x n is also completely determined, and S ⊕ realises a permutation of X. The graph ξ ⊕ is thus composed of disconnected cycles. Following Proposition 7, we have s) , and

u i = u ς i-n ⊕ u ς (s) i-n+q . Let us remark that • either ς = ς (
u i = u i-n ⊕ u i-n+q for i ≥ 1,
• or ς ̸ = ς (s) , and the sequence

(v i ) i≥1-n = (u i ⊕ 1) i≥1-n satisfies v i = v i-n ⊕ v i-n+q for i ≥ 1.
Thus either (u i ) i≥1 is a linear recurring sequence over the finite field F 2 , or both sequences (u i ) i≥1 and (v i ) i≥1 are mirroring and (v i ) i≥1 is a linear recurring sequence over F 2 . The statement of Theorem 3 is thus simplified in case of xor rule in Theorem 5: Theorem 5. The topology of ξ ⊕ depends only on n and q; in other words, the number and the lengths of the cycles of ξ ⊕ depend only on these values.

Linear recurring sequences over finite fields received an increasing interest due to the wide field of their applications, so that their mathematical properties are well known. We refer to [START_REF] Lidl | Introduction to finite fields and their applications[END_REF] for mathematical details.

The sequence u (or v depending on the (in)coherence) follows a linear recurrence relation associated to the polynomial X n + X q + 1 over F 2 . For a better readability, it is useful to recall that the order of a non constant polynomial P over F 2 is the smallest positive integer e such that P divides X e -1; the polynomial P is said to be primitive if its order is equal to 2 m -1, where m is the degree of P . Theorem 6. The synchronous dynamics of the chorded circuit CC ⊕ n,q (ε 1 , . . . , ε n ; ε (s) n-q ) involves one stable state, (0, . . . , 0) if ς = ς (s) , and (1, . . . , 1) otherwise. The state s) , and the state (0, s) , lead to a cycle of maximal length r * of ξ ⊕ , where r * is the order of the polynomial X n + X q + 1 over F 2 . The length r of any other cycle divides r * .

x * = (1, 0 ε 1 , 0 ε 1 ε 2 , . . . , 0 ε 1 ...ε n-1 ) in the case ς = ς (
1 ε 1 , 1 ε 1 ε 2 , . . . , 1 ε 1 ...ε n-1 ) in the case ς ̸ = ς (
In the particular case where P is irreducible, all the cycles other than the one reduced to the stable state have same length, equal to r * . Moreover, if the polynomial X n + X q + 1 is primitive, then ξ ⊕ is composed of two cycles, a cycle of length 1 corresponding to the stable state, and a cycle of length r * = 2 n -1. show that it is sufficient to study the stable states of CC ∧ n,q (+1, . . . , +1; +1), which gives the state (0, . . . , 0).

In the case ς = ς (s) , the state x * = (1, 0 ε 1 , 0 ε 1 ε 2 , . . . , 0 ε 1 ...ε n-1 ) defines a sequence (u i ) i≥1-n which is the so called "impulse response sequence in F 2 satisfying u i = u i-n ⊕ u i-n+q ". In the case ς ̸ = ς (s) , the state (0, 1 ε 1 , 1 ε 1 ε 2 , . . . , 1 ε 1 ...ε n-1 ) defines a sequence (u i ) i≥1-n which leads to a sequence (v i ) i≥1-n defined as above, and

(v i ) i≥1-n is the impulse response sequence in F 2 satisfying v i = v i-n ⊕ v i-n+q .
Then the proposition is easy to check from well known properties of linear recurring sequences over F 2 (see [START_REF] Lidl | Introduction to finite fields and their applications[END_REF]).

Some illustrative examples of values of n and q are presented below.

Example 1. Tables of primitive binary trinomials are available (see [START_REF] Hansen | Primitive polynomials over finite fields[END_REF]), in connection with research on random numbers generators and Mersenne prime numbers. For instance, for (n, q) = (5, 2), (9, 4), (41, 3), (98, 11), (998, 121), (1508, 599)..., the trinomial X n +X q + 1 is primitive, and ξ ⊕ includes a cycle of length 2 n -1. The same holds for X n + X n-q + 1, i.e. for (n, q) = (5, 3), (9, 3), (41, 38), (98, 87), (998, 877), (1508, 909)... Example 2. If n = 6 and q = 1 or 5, then X n + X q + 1 is primitive of order 63, which gives 1 stable state and 1 cycle of length 63.

If n = 6 and q = 3, then X n + X q + 1 is irreducible of order 9, which gives 1 stable state and 7 cycles of length 9.

If n = 6 and q = 2 or 4, then

X n + X q + 1 = (X n 2 + X q 2 + 1) 2 , where X n 2 + X q 2 +
1 is primitive of order 7, and X n + X q + 1 is of order 14, which gives 1 stable state, 1 cycle of length 7 and 4 cycles of length 14.

Asynchronous dynamics

This section is devoted to the complete description of asynchronous graphs ξ a and ξ ⊥ a , and their comparison. This relies on the structure of ξ and ξ ⊥ .

Asynchronous dynamics of the isolated circuit

C n (ε 1 , . . . , ε n ) Theorem 7.
The topology of ξ a depends only on n and the sign ς of C n (ε 1 , . . . , ε n ); in particular the number and the nature of attractors of the asynchronous dynamics depend only on these values.

Proof. Let us consider two circuits C n (ε 1 , . . . , ε n ) and C n (ε ′ 1 , . . . , ε ′ n ) of sign ς, and let us denote S and S ′ the related transformations. Then, given initial conditions (u 1-n , . . . , u 0 ), the sequences (u i ) i≥1-n introduced in Proposition 6 are the same for both circuits, but associated to the iterates

of the states x = (u 0 , u ε 1 -1 , u ε 1 ε 2 -2 , . . . , u ε 1 ...ε n-1 1-n ) and x ′ = (u 0 , u ε ′ 1 -1 , u ε ′ 1 ε ′ 2 -2 , . . . , u ε ′ 1 ...ε ′ n-1 1-n ) respectively. Thus the synchronous graph of C n (ε ′ 1 , . . . , ε ′ n ) is obtained from the one of C n (ε 1 , . . . , ε n ), keeping the edges, by a one-to-one transformation τ of the set X = {0, 1} n of nodes associating x ′ to x. More precisely, τ is defined by τ (x 1 , . . . , x n ) = (x 1 , x ε 1 ε ′ 1 2 , . . . , x ε 1 ...ε n-1 ε ′ 1 ...ε ′ n-1 n
), and satisfies τ • S = S ′ • τ . This implies that for i ∈ {1, . . . n} the equality (S(x)) i ̸ = x i is equivalent to (S ′ (τ (x))) i ̸ = x i , namely that U pd S (x) = U pd S ′ (τ (x)), and proves that the topology of the related asynchronous graphs are the same.

Remark 8. Remark that Theorem 7 can be extended. First, the result does not depend of the choice of the updating rules. Moreover, the map τ involved in the proof of Theorem 7 satisfying Lemma 3. Let us assume that k ̸ = 0 and k ̸ = n. If a state x satisfies the condition U pd S (x) = {1, . . . , k}, then there exists a path in ξ a from x to the state x.

Proof. By Proposition 12, there is a path in ξ a from x towards a state x (1) for which U pd S (x (1) ) = {1, . . . , k -1, k + 1}, a path from x (1) towards a state x (2) for which U pd S (x (2) ) = {1, . . . , k -2, k, k + 1}, and so on, until a path from a state x (k-1) towards a state x (k) for which U pd S (x (k) ) = {2, . . . , k + 1}. At this step of the process, with the notation x = (x 1 , . . . , x n ), we have x (k) = (x 1 , . . . , x k , x k+1 , . . . , x n ). A path then links in ξ a the state x (k) towards a state x (k+1) = (x 1 , . . . , x k+1 , x k+2 , . . . , x n ) for which U pd S (x (k+1) ) = {2, . . . , k, k+2} ; a path links x (k+1) towards a state x (k+2) = (x 1 , . . . , x k+2 , x k+3 , . . . , x n ) for which U pd S (x (k+1) ) = {2, . . . , k, k+3}, and so forth until x, for which U pd S (x) = {1, . . . , k}.

Lemma 4. Let's assume that k ̸ = 0 and k ̸ = n. If a state x satisfies the condition #U pd S (x) = k, then there exists a path in ξ a from x towards the state x.

Proof. By Lemma 2, there exists in ξ a a path from x towards a state y for which U pd S (y) = {1, . . . , k}, and a path from y towards a state z for which U pd S (z) = U pd S (x). Proposition 3 then gives z = x or z = x. In the case z = x, we have obtained a path from x towards x. In the case z = x, there is a path from y towards y by Lemma 3. To a path from y towards z, given by Lemma 2 and denoted by y → y

(1) → • • • → y (r) → z = x , relates a path y → y (1) → • • • → y (r) → z = x,
and we have obtained in the second case a path from x towards x, which completes the proof.

Theorem 8. The asynchronous graph ξ a is connected.

1. For k = 0 and k = n, the vertices of the kth level of the synchronous graph ξ (if this level exists) form the strongly connected components of ξ a reduced to a single vertex.

2. When k ̸ = 0 and k ̸ = n, the vertices of the kth level of the synchronous graph ξ (if this level exists) form a strongly connected component of ξ a .

Proof. We see at once the cases k = 0 and k = n, which are clear from Proposition 12. The previous study of the levels of ξ (see Proposition 3) and Lemmas 2-4 establish the fact that for k ̸ = 0 and k ̸ = n the vertices of the kth level of the synchronous graph ξ (if this level exists) form a strongly connected subgraph of ξ a . Proposition 12 then shows that the only edges between strongly connected components of ξ a reduced to a single vertex and strongly connected subgraphs of ξ a formed by the vertices of the other levels of ξ link vertices of the kth level towards vertices of the (k -2)th level: this proves that the asynchronous graph ξ a is connected, and completes the proof.

Consequently, one has the following proposition, describing the attractors.

Proposition 14. The attractors of the asynchronous dynamics of C n (ε 1 , . . . , ε n ) are two stable states in the case of a positive isolated circuit, and a single cyclic attractor in the case of a negative isolated circuit.

Asynchronous dynamics of the chorded circuit CC

⊥ n,q (ε 1 , . . . , ε n ; ε (s) n-q )
First of all, as already noted, we show that the topology of the asynchronous graph ξ ⊥ a of S ⊥ depends essentially on the signs of the associated isolated circuits.

Theorem 9. The topology of ξ ⊥ a depends only on n, q and the signs ς of C n (ε 1 , . . . , ε n ) and ς (s) of C n-q (ε 1 , . . . , ε n-q-1 , ε (s) n-q ); in particular, the number and the nature of attractors of the asynchronous dynamics of CC ⊥ n,q (ε 1 , . . . , ε n ; ε (s) n-q ) depend only on these values.

Proof. The proof is the same as that of Theorem 7, considering chorded circuits

CC ⊥ n,q (ε 1 , . . . , ε n ; ε (s) n-q ) and CC ⊥ n,q (ε ′ 1 , . . . , ε ′ n ; ε ′ (s)
n-q ) such that the signs of the related associated isolated circuits are the same, and their related transformations S ⊥ and S ⊥ ′ .

Then, given initial conditions (u 1-n , . . . , u 0 ), the sequences (u i ) i≥1-n introduced in Proposition 7 are the same for both Remark 10. Here again, the proof shows more generally that the topology of the state transition graph of CC ⊥ n,q (ε 1 , . . . , ε n ; ε (s) n-q ) depends only on n, q, on the sign ς of C n (ε 1 , . . . , ε n ) and on the sign ς (s) of C n-q (ε 1 , . . . , ε n-q-1 , ε (s) n-q ), whatever the choice of updating rules defining the dynamics.

In the following proposition, we describe the modifications in order to obtain the asynchronous graph ξ ⊥ a of S ⊥ from the asynchronous graph ξ a of S. The dynamics is modified only for the scs-states, in the following way:

Proposition 15. Let us denote by E(ξ a ) (resp. E(ξ ⊥ a )
) the set of edges of ξ a (resp. ξ ⊥ a ).Then, for every scs-state x,

• if (x, x 1 ) ∈ E(ξ a ), then (x, x 1 ) ̸ ∈ E(ξ ⊥ a ); • if (x, x 1 ) ̸ ∈ E(ξ a ), then (x, x 1 ) ∈ E(ξ ⊥ a ).
Proof. Given a state x, let us recall that

S ⊥ (x) = { S(x) 1 if x is a scs-state, S(x)
otherwise. Proposition 15 is an immediate consequence of these equalities.

Remark 11. If n -q ̸ = 1, the transformation described in Proposition 15 remains to inverse the edges between the pairs of scs-states of the form {x, x 1 }.

If nq = 1 (self-regulation of g 1 ), the transformation described in Proposition 15 remains, for every scs-state x, to delete the edge between x and x 1 if ε (s) 1 = +1, and to add one if ε

(s) 1 = -1 .
Hence, ξ ⊥ a can easily be deduced from ξ a , applying the modifications described above.

Notations 2.

• Elements of sets U pd S (x) are considered modulo n.

• {1, . . . , n} +1 represents the subset of the even integers of {1, . . . , n}.

• {1, . . . , n} -1 represents the subset of the odd integers of {1, . . . , n}.

• As before, ς stands for the sign of C n (ε 1 , . . . , ε n ).

• For ς ∈ {-1, +1}, k ∈ {1, . . . , n} ς and i ∈ {0, 1}, we denote by z (k,i) the state such that z (k,i) 1

= i, and U pd S (z (k,i) ) = {n -k + 2, . . . , n -1, n, 1} (Proposition 4 ensures the existence of such a state). Hence, #U pd S (z (k,i) ) = k.

In addition, if ς = +1 and i ∈ {0, 1}, we denote by z (0,i) the states s.t. z (0,i) 1 = i, and U pd S (z (k,i) ) = ∅ (stable states with respect to S).

The interest of introducing these states appears in the following lemmas and propositions, giving valuable information on the structure of ξ ⊥ a .

Lemma 5. If k ≥ 2, there is an edge from z (k,i) to z (k-2,i) common to ξ a and ξ ⊥ a .

Proof. This is a direct consequence of Proposition 12, and Proposition 15 and the fact that the first coordinate is not affected moving from z (k,i) to z (k-2,i) .

Lemma 6. For i ∈ {0, 1}, let x be a state such that x 1 = i and #U pd S (x) = k, with k ̸ = 0 and k ̸ = n. There exists a path from x to z (k,i) common to ξ a and ξ ⊥ a .

Proof. By Proposition 12, and considering the fact that 2 / ∈ U pd S (z (k,i) ), it is easily seen that there is a path in ξ a from x towards z (k,i) s.t. for any state y of this path #U pd S (y) = k and the first coordinate of y stays constant equal to i. This implies by Proposition 15 that the path is common to ξ a and ξ ⊥ a .

Theorem 10.

1. The asynchronous graph ξ ⊥ a is connected.

2. Moreover ξ ⊥ a involves at most two terminal strongly connected components (stable states or cyclic attractors).

3. If ς = +1, these components (distinct or not) contain respectively z (0,0) and z (0,1) . If ς = -1, theses components (distinct or not) contain respectively z (1,0) and z (1,1) .

4. Their basins of attraction contain respectively at least all states x s.t. x 1 = 0, and at least all states x s.t. x 1 = 1.

Proof. The description of terminal SCCs and basins of attraction is an immediate consequence of the previous lemmas. Item 4 of the proposition then shows that the existence of an edge in ξ ⊥ a between states differing by their first coordinate implies the connectivity of ξ ⊥ a . Except in the case n -q = 1 and ε (s) 1 = +1, Remark 11 shows that there are edges common to ξ a and ξ ⊥ a between such states. In the case n -q = 1, ε (s) 1 = +1, the scs-states are the states

x = (x 1 , . . . , x n ) s.t. x εn n ⊥ x 1 ̸ = x εn n .
Let a and b be distinct elements of {0, 1} such that a ⊥ b = a (such elements exist for ⊥∈ {∧, ∨, ⊕}). Then the state x = (b, x 2 , . . . , x n-1 , a εn ) is not a scs-state, and 1 ∈ U pd S (z (k,i) ). This completes the proof.

We are going to precise the number and the nature of these attractors in the cases of chorded circuits and, or and xor. Let us remind that stable states are the same in the synchronous and the asynchronous dynamics.

Asynchronous dynamics of the chorded circuits and and or

The Proposition 9 shows that the asynchronous dynamics of S ∨ is deduced from the one of S ∧ by mirroring, and therefore we continue to detail the case and. We recall in this case the result of Theorem 9 : the topology of ξ ∧ a depends only on n, q and the signs ς of C n (ε 1 , . . . , ε n ) and ς (s) of C n-q (ε 1 , . . . , ε n-q-1 , ε

(s) n-q ).
In the previous paragraph, we have seen how to obtain ξ ∧ a from ξ a (Proposition 15):

• If n -q ̸ = 1, we have to change the direction of the edges between the pairs of scs-states of the form {x, x 1 }.

• In the special case n -q = 1, if x is a scs-state, that is (x n , x 1 ) = (1 εn , 0 ε (s) 1 ), then x 1 is not a scs-state, S(x) = (1,

x ε 1 1 , . . . , x ε n-1 n-1 ) and S ∧ (x) = (0, x ε 1 1 , . . . , x ε n-1 n-1 ). Thus, if ε (s)
1 = 1 (self-activation of g 1 ), we have to delete the edges from all the scs-states x towards the states x 1 , and if ε (s) 1 = -1 (self-inhibition of g 1 ), we have to create edges from all the scs-states x towards the states x 1 .

The following proposition precises the number and the nature of attractors.

Proposition 16. Let ς be the sign of C n (ε 1 , . . . , ε n ), and ς (s) the sign of C n-q (ε 1 , . . . , ε n-q-1 , ε

(s) n-q ).
1. If ς = +1, the attractors of the asynchronous dynamics of the chorded circuit CC ∧ n,q (ε 1 , . . . , ε n ; ε (s) n-q ) are two stable states if ς (s) = +1, and one stable state if ς (s) = -1.

2. If ς = -1, the attractors of the asynchronous dynamics of the chorded circuit CC ∧ n,q (ε 1 , . . . , ε n ; ε (s) n-q ) are one stable state if ς (s) = +1, and a single cyclic attractor if ς (s) = -1.

Proof. From Theorem 10, the number of attractors is one or two.

1. If ς = +1 and ς (s) = +1, there exists two stable states, as proved in Theorem 4.

If ς = +1 and ς (s) = -1, Theorem 9 enables to restrict the study of attractors to the case CC ∧ n,q (+1, . . . , +1, +1; -1). In this case, the state z (0,0) = (0, . . . , 0) is stable, whereas there is an edge from z (0,1) = (1, . . . , 1) to (0, 1, . . . , 1). This implies by Theorem 10 that the stable state z (0,0) constitutes the single attractor.

2. If ς = -1, Theorem 4 shows that there is one stable state. Wathever the sign of ς (s) , one of the states z (1,i) is not a scs-state, and there is an edge of commutation of its first coordinate in ξ ⊥ a . This proves by Theorem 10 that the stable state constitutes the single attractor.

Remark 12. In other words, in the cases and and or, a coherent chorded circuit and its corresponding long circuit have the same number and type of attractors, whereas an incoherent chorded circuit has a unique attractor which is a stable state.

The dynamics of C n (ε 1 , . . . , ε n ) clearly presents a symmetry by mirroring, whatever the choice of updating rules defining the dynamics. In CC ⊥ n,q (ε 1 , . . . , ε n ; ε (s) n-q ), this symmetry is disturbed by the short cut. Let us recall that the bassin of attraction of an attractor is the set of states x for which there exists a path from x towards a state of the attractor (not including the states of the attractor). In the case ς = ς (s) = +1, we present the way the short cut creates a strict bassin of attraction for one of the two stable states of ξ ∧ a , that is a set of states that do not belong to the bassin of attraction of the other stable state.

As a matter of convenience, we first focus on the chorded circuit CC ∧ n,q (+1, . . . , +1, +1; +1). The scs-states are then the states x s.t. (x n , x q ) = (1, 0). Following the notations of the beginning of the section, let us recall that the dynamics involves the two stable states z (0,0) = (0, . . . , 0) and z (0,1) = (1, . . . , 1). More generally, z (k,0) = (0, . . . , 0, 01, . . . , 01) -with k 2 occurences of "1" -and z (k,1) = (1, . . . , 1, 10, . . . , 10) = z (k,0) , for k ∈ {1, . . . , n} +1 . Lemma 7. In the graph ξ ∧ a associated with CC ∧ n,q (+1, . . . , +1, +1; +1), all the states x / ∈ {z (0,0) , z (0,1) } are in the bassin of attraction of z (0,0) . Proof. Let us remark that the state z (2,1) = (1, . . . , 1, 0) is not a scs-state, considering that (z (2,1) ) n = 0. Thus there is an edge from z (2,1) to z (2,1) 1 in ξ ∧ a , which gives the result by Lemmas 5 and 6. Lemma 8. In the graph ξ ∧ a associated with CC ∧ n,q (+1, . . . , +1, +1; +1), the bassin of attraction of z (0,0) includes all the states x / ∈ {z (0,0) , z (0,1) }. The bassin of attraction of z (0,1) includes 2 n -2 q -1 states, so that 2 q -1 states form a strict bassin of attraction of z (0,0) . Proof. Let x be a state such that x 1 = 0 and #U pd S (x) = k, with k ≥ 2. Then the state x does not belong to the bassin of attraction of z (0,1) if and only if U pd S (x) is contained in {n -q + 1, n -q + 2, . . . , n, 1}, so that any path from x to a state y such that 1 belongs to U pd S (y) makes y be a scs-state s.t. y 1 = 0, and y 1 cannot be updated. The number of elements of the strict bassin of attraction of z (0,0) is thus ∑ 0<k≤q+1 k∈{1,...,n} +1 ( q+1 k ) = 2 q -1, by an easy calculation.

Theorem 11. In the asynchronous dynamics of the chorded circuit CC ∧ n,q (ε 1 , . . . , ε n ; ε (s) n-q ), with ς = ς (s) = +1, the bassin of attraction of one of the two stable states, denoted by z 0 , includes all the states except z 0 and the other stable state z 1 . The bassin of attraction of z 1 includes 2 n -2 q -1 states, so that 2 q -1 states form a strict bassin of attraction of z 0 .

Proof. This theorem is a direct consequence of Theorem 9 and the two previous lemmas.

Remark 13. Therefore, when the value of n is fixed, the strict bassin of attraction of z 0 is all the greater given that the circuit C n-q (ε 1 , . . . , ε n-q-1 , ε (s) n-q ) is small.

Asynchronous dynamics of the chorded circuit xor

First of all, there is an interesting corollary of Theorems 5 and 9.

Proposition 17. The topology of ξ ⊕ a depends only on n and q.

We have already describe the way to get ξ ⊕ a from ξ a (Proposition 15):

• If n -q ̸ = 1, we have to change the direction of the edges between the pairs of scs-states of the form {x, x 1 }.

• In the special case n -q = 1, if x is a scs-state, that is

x 1 = 1 ε (s) 1 , then x 1 is not a scs-state, S(x) = (x εn n , x ε 1 1 , . . . , x ε n-1 n-1 ) and S ⊕ (x) = (x -εn n , x ε 1 1 , . . . , x ε n-1 n-1 ). Thus, if x n ̸ = 1 ε (s)
1 εn , we have to delete the edge from x towards x 1 , and if x n = 1 ε (s)

1 εn , we have to create an edge from x towards x 1 .

We now precise the attractors.

Proposition 18. The attractors of the asynchronous dynamics of the chorded circuit CC

⊕ n,q (ε 1 , . . . , ε n ; ε (s)
n-q ) are reduced to a single stable state.

Proof. Proposition 17 enables to restrict the study of attractors to CC ∧ n,q (+1, . . . , +1, +1; +1). In this case, the state z (0,0) = (0, . . . , 0) is a stable state, and there is an edge from z (0,1) = (1, . . . , 1) to z (0,1) 1 = (0, 1, . . . , 1) in ξ ⊕ a . Then Theorem 10 and previous lemmas give the result.

Remark 14. Hence, in the case of the xor logical rule, the asynchronous STG of a chorded circuit encompasses a unique stable state as sole attractor, as in the case of incoherent chorded circuits and and OR. This should be related to the fact that using a xor rule amounts to introduce dual regulations, which may be considered as a particular case of incoherent chorded motif.

Conclusion

Biological networks, and in particular regulatory networks, are more and more large and complex, integrating the huge quantity of biological data and knowledge increasingly available. Hence, even using qualitative formalisms as Boolean models, we face combinatorial explosion problem keeping us from doing exhautive analysis. Among strategies used to cope with this problem, functional motifs analysis is useful and efficient to understand the emergence of dynamical properties and identify the main actors. Circuits are basic structures of such motifs, as they are known to be necessary for the appearance of complex dynamical properties (as multistability or sustained oscillations). The work presented here gives an exhaustive, precise and general description of the Boolean dynamics of circuits and chorded circuits. The use of combinatorics, group actions and graph theory make links between synchronous and asynchronous dynamics, and emphasize features of the structure of the STG (e.g. symmetries). The dynamics of isolated and chorded circuits depend only on few parameters (the length, sign and logical rules for chorded circuits).

This work paves the way for studies of more general and complex motifs, by adding edges or coupling circuits for instance. A fine knowledge of the proper dynamics of isolated motifs is a prerequisite for the study of their functionality, i.e. to know if they keep their dynamical properties when embedded in a large graph, and in which conditions. Furthermore, this study point out invariants that lead to a classification of boolean FDS relying on these invariants. Thus, the study of all the dynamics could be reduced to a representative per class, as emphasized in the proofs hereby. In fine, the analysis of complex regulatory networks can be eased by a decomposition in modules (or motifs) whose dynamics is exhaustively described. This leads to the problem of recomposition of networks (functionality of modules).

Proof.

  According to previous proposition and remarks, the equalities a⊕b = ā⊕ b and a ⊕ b = a⊕ b

Figure 4 :

 4 Figure 4: Regulatory graphs and their synchronous dynamics, with and or xor rules for chorded circuits. (I) a 4-components positive isolated circuit; (II) a coherent positive chorded circuit; (III) an incoherent chorded circuit; (IV) a positive circuit with a coherent self-regulation. Colors distinguish the disjoints synchronous cycles of the STG of the isolated circuit, and the way they are spread in the different cases of chorded circuits. Dashed arrows stand for transitions with more than two updated components; red arrows represent transitions with only one component updated (conserved in the asynchronous STG).

Figure 5 :Figure 6 :

 56 Figure 5: Regulatory graphs and their synchronous dynamics, with and rules for chorded circuits. (I) a 4-components negative isolated circuit; (II) a coherent chorded circuit; (III) an incoherent chorded circuit; (IV) a negative circuit with a coherent self-regulation. Colors distinguish the disjoints synchronous cycles of the STG of the isolated circuit, and the way they are spread in the different cases of chorded circuits. Dashed arrows stand for transitions with more than two updated components; red arrows represent transitions with only one component updated (conserved in the asynchronous STG).

Isolated circuits and/or chorded circuits xor chorded circuits

		Vertex-disjoint cycles	Terminal cycles	Vertex-disjoint cycles
		In each cycle, states with		Long pseudo-random
		the same number of		cycles
		updating calls		One stable state
	Synchronous STG	Positive circuits Even numbers of updating calls Two stable states	Positive long circuits Terminal cycles from the synchronous STG of the long circuit • Coherent chorded circuit Two stable states • Incoherent chorded
			circuit
			One stable state
		Negative circuits	Negative long circuits
		Odd numbers of	• Coherent chorded
		updating calls	circuit
		No stable state	No stable state
			• Incoherent chorded
			circuit
			One stable state
		Connected level structure	Deduced from the	Deduced from the
		Levels form the SCCs	asynchronous STG of the	asynchronous STG of the
		(except perhaps for the	long circuit	long circuit
		two extremal levels), and	→ deleting or creating	→ deleting or creating
		gather states with the	edges if the short-circuit is	edges if the small circuit is
		same number of successors	a self-loop	a self-loop
			→ inverting edges	→ inverting edges
			otherwise	otherwise

Asynchronous STG Positive circuits Even numbers of successors Two stable states Positive long circuits • Coherent chorded circuit Two stable states

	3.
		One stable state
		• Incoherent chorded
		circuit One stable state
	Negative circuits:	Negative long circuits
	Odd numbers of	• Coherent chorded
	successors	circuit One terminal
	One terminal SCC	SCC
		• Incoherent chorded
		circuit One stable state
	Figure 2: Comparison of the structure of boolean synchronous and asynchronous dynamics of
	isolated circuits (first column) and chorded circuits (second and third columns). SCC stands for
	Strongly Connected Component.

1 Synchronous dynamics of the isolated circuit C

  n (ε 1 , . . . , ε n )

S ′ = τ • S • τ -1 is an isometry of the hypercube [0, 1] n , being composed of hyperplane symmetries transforming a state (x 1 , . . . , x n ) into x j = (x 1 , . . . , x j-1 , x j , x j+1 , . . . , x n ) for some fixed element j of {1, n}. Hence, for a fixed sign, the asynchronous dynamics associated to C n (ε 1 , . . . , ε n ) are isometrical [Glass, 1975].

Let us recall that the synchronous graph ξ of C n (ε 1 , . . . , ε n ) is composed of disconnected cycles which can be gathered into levels, and that the kth level is made up of the states x for which U pd S (x) has k elements. As we demonstrate below, these levels play a significant role in the structure of the asynchronous graph ξ a .

The sets U pd S (x) are contained in {1, . . . , n}, and until the end of this paragraph we consider these integers modulo n.

Proposition 12. If there is an arc in ξ a from the state x = (x 1 , . . . , x i-1 , x i , x i+1 , . . . , x n ) towards the state y = (x 1 , . . . , x i-1 , x -1 i , x i+1 , . . . , x n ), then we have:

In particular, #U pd S (y) = #U pd S (x) or #U pd S (y) = #U pd S (x) -2.

Proof. We recall (cf. proof of Proposition 3) that a state x and its corresponding set U pd S (x) are linked for j = 1, . . . , n through the equalities

, where

We define in the same way the numbers η j (y). As states x and y differ only on the ith coordinate, we have η i-1 (x) = -η i-1 (y), η i (x) = -η i (y), and η j (x) = η j (y) for all j / ∈ {i -1, i}. We deduce U pd S (y) from these equalities.

Remark 9. Proposition 12 can be seen as a circular abacus in which each movement corresponds to an arc of ξ a . Hence, each path in ξ a can be coded with an initial state x (1) together with the sequence of movements trigged in the abacus U pd S (x (1) ), . . . , U pd S (x (k) ).

The following proposition and lemmas are used to provide the complete description of the strongly connected components of ξ a . Proposition 13. If there is an arc in ξ a from the state x towards the state y, then there is an arc from the state S(x) towards the state S(y).

n-1 ) and we have seen that i + 1 ∈ U pd S (S(x)) (cf. Proposition 2). Hence, there is a link from x towards y

n-1 ) in the graph ξ a . We just have to remark that z = S(y) in order to conclude.

Lemma 2. Let's assume that k ̸ = 0 and k ̸ = n, and let P 1 and P 2 be subsets of {1, . . . , n} with k elements. Then for any state x for which U pd S (x) = P 1 , there exists a path in ξ a from x towards a state y for which U pd S (y) = P 2 .

Proof. By Proposition 12 above, it is easily seen that there is a path in ξ a from x towards a state z for which U pd S (z) = {1, . . . , k}, and a path from z towards a state y for which U pd S (y) = P 2 .

A Appendix Hierarchical Transition Graph of circuits and chorded circuits: a compressed representation of the asynchronous dynamics

When possible, it is useful to generate the Hierarchical Transition Graph (HTG), a compressed representation of the dynamics [START_REF] Bérenguier | Dynamical modeling and analysis of large cellular regulatory networks[END_REF]. It provides a large scale vision of the trajectories, emphazing the main switches and cyclical behaviours, and loosing the detailed information of the STG. Its construction is in the same vein as the strongly connected component graph, for which each node represents all the nodes of the STG belonging to a same complex strongly connected component (SCC). But asynchronous STGs generated from biological networks used to contain many "single SCCs" (i.e. composed of only one element) and the SCC graph remains large. The HTG compresses further the graph by gathering all the single SCCs leading to the same complex SCCs and attractors. There is an edge between two nodes H 1 and H 2 of the HTG if and only if there exists an edge in the STG between an element of H 1 and an element of H 2 (see [START_REF] Bérenguier | Dynamical modeling and analysis of large cellular regulatory networks[END_REF] for more details). Thus, HTG provides an efficient compressed visualisation of the STG, and thereby emphasizes the main structure and key decision points of the dynamics.

In the case of circuits and chorded circuits, the structure of the HTG can be easily achieved by the description of the asynchronous graph; significant examples are shown in Figure 6 0 1 1 0 1 1 1 0 1 x (scs) 1 1 1 0 1 (scs) 0 1 1 1 0 (scs) 1 0 1 1 1 0 1 0 1 1 (scs) 1 0 1 0 1 0 1 0 1 0 (scs) 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 (scs) 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 (scs) 1 0 1 0 0 1 1 0 1 0 (scs) 0 1 1 0 1 (scs) 0 0 1 1 0 1 0 0 1 1 1 1 0 0 1 (scs) 1 1 1 0 0 (scs) 1 1 1 1 0 (scs) 1 1 1 1 1 (scs) 0 1 1 1 1 (scs) 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 (scs) 0 1 1 0 0 (scs) 1 0 1 1 0 1 1 0 1 1 x (scs) 1 1 1 0 1 Figure 3: Iterations of the synchronous transformations These arrays represent the synchronous trajectories from the state x. Left: isolated circuit C(n = 14, ς = +1); Center: chorded circuit with and rule CC ∧ (n = 14, q = 9, ς (s) = +1, ς = +1); Right: chorded circuit with xor rule CC ⊕ (n = 5, q = 2). The short-cut sensitive states are indicated with the abbreviation (scs), the stable state with ss.