# Boolean automata isolated cycles and tangential double-cycles dynamics

Jacques Demongeot 1, , Tarek Melliti 2, , Mathilde Noual 3, ,
Damien Regnault 2, and Sylvain Sené 4,
1 Université publique, Grenoble, France
2 Université publique, Évry, France
3 Freie Universität Berlin, Germany
4 Université publique, Marseille, France
jacques.demongeot@univ-grenoble-alpes.frtarek.melliti@univ-
evry.frmathilde.noual@incaseofpeace.comdamien.regnault@univ-
<EMAIL_ADDRESS>
###### Abstract

Abstract Our daily social and political life is more and more impacted by
social networks. The functioning of our living bodies is deeply dependent on
biological regulation networks such as neural, genetic, and protein networks.
And the physical world in which we evolve, is also structured by systems of
interacting particles. Interaction networks can be seen in all spheres of
existence that concern us, and yet, our understanding of interaction networks
remains severely limited by our present lack of both theoretical and applied
insight into their clockworks. In the past, efforts at understanding
interaction networks have mostly been directed towards applications. This has
happened at the expense of developing understanding of the generic and
fundamental aspects of interaction networks (properties and behaviours due
primarily to the fact that a system is an interaction network, as opposed to
properties and behaviours rather due to the fact a system is a genetic
interaction network for instance). Intrinsic properties of interaction
networks (_e.g._ , the ways in which they transmit information along entities,
their ability to produce this or that kind of global dynamical behaviour
depending on local interactions) are thus still not well understood. Lack of
fundamental knowledge tends to limit the innovating power of applications.
Without more theoretical fundamental knowledge, applications cannot evolve
deeply and become more impacting. Hence, it is necessary to better apprehend
and comprehend the intrinsic properties of interaction networks, notably the
relations between their architecture and their dynamics and how they are
affected by and set in _time_. In this chapter, we use the elementary
mathematical model of Boolean automata networks as a formal archetype of
interaction networks. We survey results concerning the role of feedback cycles
and the role of intersections between feedback cycles, in shaping the
asymptotic dynamical behaviours of interaction networks. We pay special
attention to the impact of the automata updating modes.
_Keywords:_ Discrete dynamical systems, Boolean networks, Boolean cycles,
updating modes, dynamics and combinatorics.

##  1 Introduction

Interaction networks occupy an important place in our daily life. We see this
today in particular with the massive use of social networks, the fundamental
implications and mechanisms of which we hardly have any understanding of. And
social media is just one example among many other kinds of interaction
networks that affect us consequentially. At all levels of our lives there are
interaction networks, that can be comprised as sets of entities that interact
locally with each other over time.

In an interaction network, local interactions take place. And as a result of
these, the network as a whole exhibits global behaviours that generally remain
difficult to explain on the sole basis of local processes. Undeniably one of
the most telling examples lies at the origin of all living organisms: genes
and their regulation, associated with other mechanisms inducing variability
(splicing, role of the chromatin, _etc._). It is currently accepted in biology
and medicine, that a better understanding of genetic regulation is a necessary
condition for improving our knowledge of life, which in turn could allow us to
achieve a more precise comprehension of pathologic mechanisms, and to access
more targeted and thereby more efficient therapies.

Whilst the application aspects of interaction networks are obviously of real
and tangible importance, and they have progressed quantitatively at a frantic
pace over the last twenty years, the more fundamental aspects aiming at
understanding and analysing the intrinsic properties of these networks have so
far received less attention from the scientific community. Current
applications, in particular those emerging in biology (the privileged domain
of application of the present chapter), are awaiting significant theoretical
advances to continue their qualitative development. Undoubtedly, such
theoretical advances may be the fruit of the combination of computer science
and discrete mathematics. Together with bioinformatics, viewed here as ``the
study of computer processes in biotic systems'' [HH70, HH78], they seem
particularly suited to meet the needs arising from applications. Indeed, real
networks, through the entities and interactions that compose them, can
naturally be viewed as discrete objects. They can easily be represented by
computer models which capture their essence thanks to a high level of
abstraction. Where traditional (continuous) mathematical modelling focuses
mainly on the quantitative characteristics of networks, the interest of
discrete computer science modelling comes from the qualitative nature of the
questions that it raises, which makes it possible to realise that the central
elements of networks are not the entities themselves but rather the
interactions that link them.

This survey adopts the qualitative point of view of fundamental computer
science to examine some properties of interaction networks. This choice of
approach is consistent with the origins of modern computing. Indeed,
investigations of formal neural networks [MP43] and cellular automata [von66]
in the 1940s, both strongly inspired by natural processes, helped establish
the first links between data processing and biology. Also, the pioneering work
of McCulloch and Pitts introduced automata networks as a fundamental model of
interaction networks. For reasons discussed later, we choose to rely on the
same model here.

We thus here study automata networks, and more specifically Boolean automata
networks, from a fundamental point of view interested in developing a
qualitative understanding of networks. We focus on understanding how feedback
cycles that are part of network architectures, come to influence the
asymptotic dynamical properties of these networks. By way of methods from
discrete dynamical systems theory, enumerative combinatorics, algorithms and
complexity theory, we explore the behavioural diversity of cycles and their
tangential intersections.

Another point of focus in this chapter is how updating modes influence cycles
and cycle intersections (and this network behaviours). From both the
fundamental and the applied points of view, updating modes are known to be of
decisive importance in the shaping of a network's behaviour. Updating modes
define the way in which the states of the automata of a network are updated as
a function of a discrete time. The time being unbounded towards the future,
there is an infinite number of different possible updating modes which we can
come with and update the automata of a network according to. We focus here on
the two modes that are the most customary in the literature: the parallel mode
and the asynchronous mode. The parallel mode is a deterministic and periodic
mode. At each time step, it updates the states of all the automata in a
network. The asynchronous mode is a non-deterministic mode. It allows for any
possible series of sequential updates – which update exactly one automaton per
time step – to take place. We show how the differences between these two
updating modes imply profound differences in the network dynamics.

This chapter is a synthesis of results about interaction cycles and variations
of interaction cycles derived since the early 2000s. The list of results
presented here is not exhaustive. Details and demonstrations of these results
can be found in the literature [DNS12, MNR+15, Nou12b, RMCT03, Sen12].

We will start with a presentation of the history of automata networks in the
context of modern fundamental computer science, including a mention of the
links that this science has always entertained with biology. Main definitions
and notations will be explained after that. Then, we will briefly present
seminal results obtained in the 1980s that highlight the crucial importance of
the role of feedback cycles on the dynamical expressiveness and behavioural
diversity of interaction networks. This will lead us to focus on the dynamical
and combinatorial properties of isolated cycles when they are subjected to the
parallel and asynchronous updating modes. And finally, before concluding, we
will take a step towards contextualising cycles and look into tangential
intersections of cycles, called ``tangential double-cycles'' for short.

##  2 Automata networks: between fundamental computer science and biology

Automata network research is part of natural computation field in computer
science. And the scope of natural computation is twofold. First, it designs
and develops models of computations that draw inspiration from natural
phenomenology. Second, it manipulates such models so as to build up a firm,
albeit necessarily incomplete, grasp of biological reality natural phenomena.
As mentioned above, automata networks were initially introduced as a
theoretical model of neural networks. And since the late 1960s, the literature
evidences that they are also relevant as models of genetic regulation
networks. In this section, we provide a comprehensive overview of the
interconnections between computer science and biology manifested through
automata networks.

###  2.1 Biology as an inspiration for modern computer science

Generally, when we are interested in the history of the so-called modern
computer science, we go back to the 1930s. This period saw the development of
classical computing paradigms such as the recursive functions of Herbrand and
Gödel, the main works of which are available in [Göd86], the lambda-calculus
developed initially in [Chu32], and also the Turing machines [Tur36]. However,
to think of modern computer science only in terms of these paradigms is to
forget a whole family of less conventional models that have grounded many
developments in computer science of relevance today. This is the family of
automata networks that we mainly owe to McCulloch and Pitts, and von Neumann,
whose first elements of the theory date from the 1940s. Based on advances at
the time, the original works [MP43, von66] highlight a desire to develop the
science of computation while inspiring and advancing the modelling of natural
biological phenomena. Thus, McCulloch and Pitts introduced the model of formal
neural networks which provides an abstraction of neural interactions. They
showed in particular that propositional logic can represent neural events and
that these networks can be considered, to a certain extent, as a universal
model of computation. A little later, in the late 1940s, von Neumann developed
cellular automata in order to ``compare natural and artificial automata'' and
``abstract the logical structure of life''. The result of his work was the
construction of the first self-reproducing and universal cellular automaton.

Formal neural networks and cellular automata constitute the founding base of
the theory of automata networks, an automata network being defined ``roughly''
as a set of entities (automata) which interact with each other. Their
interactions happen in a discrete time, according to transition functions
which are local to the entities. The two major differences that distinguish
these two models relate to the number of interacting entities and the nature
of the network on which the entities are placed. Indeed, cellular automata are
defined by default as having an infinite number of entities (a.k.a. cells).
And the entities are placed on a regular and homogeneous network (in general
$\mathbb{Z}^{d}$, with $d>0$). Formal neural networks (also called threshold
Boolean automata networks) have a finite number of entities. And the entities
are placed on an irregular and heterogeneous network. These differences give
to each of these models its own characteristics that have enabled strong
advances in computer science.

By their infinite nature, cellular automata have been mainly studied for their
computability properties. Among them, we find the Turing universality of the
self-reproducing automaton [von66], of the Game of Life of Conway [BCG82] and
of the elementary cellular automaton 110 [Coo04]. Also, in 1971, Smith showed
that any Turing machine could be simulated by a cellular automaton defined on
$\mathbb{Z}$ [Smi71]. In addition, cellular automata proved to be good
mathematical tools for studying the parallel functioning of computers, of
which they were at the origin of systolic architectures [KL80]. Finally,
within the framework of dynamical system theory, the desire to understand
their behavioural diversity was at the origin of studies of complexity [Wol84,
Kur97]. Formal neural networks have also brought a lot of progress. In their
original article, McCulloch and Pitts showed that they can simulate any
Boolean function. Kleene resumed this work. Based on their finite nature, he
proved that the languages recognised by these objects are regular, which also
allowed him to introduce the concept of finite automata [Kle56]. Behavioural
characterisation conditions were also given and algebraic methods were then
developed within this framework [Huf59, Els59, Gol67, Cul71]. This last
reference highlights in particular, strong links between these networks and
the Boolean model of genetic regulation networks introduced in [Kau69a,
Kau69b]. This latter model is at the origin of numerous works emphasising the
interest taken by computer science in the context of research in theoretical
biology.

###  2.2 Computer science as a methodological source for biology

Understanding the mechanisms of biological regulation, in all their diversity,
is one of the major current problems in molecular biology. This was notably
highlighted by Jacob and Monod in the early 1960s, in particular in [JM61,
MCJ63]. However, from the end of the 1960s, an observation was shared by two
biologists, Kauffman (biochemist and biophysicist) and Thomas (biochemist and
geneticist). The usual methods of treatment stemming from molecular biology
are not adapted to treat as a whole such a problem at the genetic level.
According to them, the experimental nature of the methods specific to biology
at the time can only provide a piecemeal response to this problem and needs to
be supplemented by methodological approaches. On the basis of Delbrück's work,
according to which there are links between differentiated cell types and the
attractors of theoretical network models [Del49], Kauffman and Thomas proposed
to use discrete mathematics to go beyond simple observational knowledge of
regulatory systems, advocating in a sense that biology must move towards more
general and systematic approaches to living things. This resulted in two
articles which organise and federate a whole section of research at the
frontier between discrete mathematics and theoretical biology [Kau69a, Tho73].

Kauffman is thus the first to have proposed a model of genetic regulatory
networks, based on formal neural networks. This model is known as _Boolean
networks_. It is a formalisation of regulation where genes are the vertices of
a randomly constructed graph. Genes interact over time (discrete). Their
interactions are dictated by local Boolean transition functions. They
determine whether the genes can be expressed or not, that is to say,
transcribed or not [Kau71]. Originally, this model is based on two strong
hypotheses: the interactions are based on an architecture of $k$-regular
graphs, namely graphs of which all the vertices have the same number of
neighbours; the evolution is perfectly synchronous (or parallel). Relaxations
of these hypotheses were subsequently carried out [Ald03, Ger04]. They gave
rise to applications to biological problems such as the analysis of the
behaviour of the yeast regulatory network [KPST03], and more generally to the
analysis of signalling networks [GBK+07, Alb09]. In 1973, Thomas opposed the
parallelism hypothesis and developed another method that sought to be closer
to ``genetic reality'' [Tho73]. This method comes with two new ideas. The
first proposes to represent the causal dynamics of genetic regulations by
means of an asynchronous state transition system. The second idea is to
represent the networks themselves by digraphs whose arcs are signed according
to the promoting or inhibiting nature of interactions. In [Tho81], Thomas
introduces two fundamental conjectures, proven in the discrete framework in
[RC07, Ric10]. The first one (resp. The second one) states that the presence
of a positive cycle (resp. of a negative cycle), composed of an even number
(resp. an odd number) of inhibitory edges, in the architecture of the network
is necessary for dynamical multi-stationarity (resp. for the existence of an
oscillating limit regime). Beyond theoretical research, this method has been
widely applied in biology, such as for example the immune response [KT85,
Men06, SRSL+07] or to infection of _Escherichia coli_ by $\lambda$ phage
[TTK95, TT95, GEHL02].

Although they were initiated by scientists from biology, these two visions
emphasise the relevance of automata networks and thus bear the mark of
computer science and discrete mathematics. The contribution of mathematician
F. Robert played a key role. From the end of the 1960s he pioneered the study
of automata networks from a more fundamental and formal point of view. Indeed,
Kauffman and Thomas made ``arbitrary'' choices regarding the ways of updating
the automata over time. But Robert was interested in the updating modes as
such and their influences on the networks behaviours. He formalised the
concepts of block-sequential iterations and chaotic iterations [Rob69, Rob76,
Rob80, Rob86, Rob95], which make it possible to obtain updating modes that are
partly synchronous and asynchronous. This makes perfect sense in theoretical
biology since there is no biological argument today to define the temporal
organisation of genetic regulations. In addition, the work carried out by
Robert and his collaborators made it possible to establish solid theoretical
bases (simple and general) for the behavioural study of automata networks
[Gol82, CD85, GFSP85, GM90] while keeping in mind their representational
capacities for biology [Dem75, CDLB83, DGT85]. In this theoretical framework,
Robert proved the essential role played by cycles in defining the intrinsic
behavioural properties of networks: his theorem stipulates that any acyclic
network has a trivial behaviour and admits to the temporal asymptote only a
single point fixed. Again, Robert's work has found many applications in
biology, including modelling the genetic control of the flower development of
_Arabidopsis thaliana_ [MAB98, DGM+10, RGS18] and the study of ventral
invagination during gastrointestinal morphogenesis in Drosophila [AGZ+06].

###  2.3 Boolean automata networks, a simple but complex model

From a general point of view, automata networks can be used to model any
system which satisfies the following three properties:

  * •

It is made up of distinct entities that interact with each other;

  * •

Each entity is characterised by a variable quantity, which precisely calls to
be translated in terms of states of the corresponding automaton in the model;

  * •

The events undergone by the system, like the mechanisms that are at their
origin, cannot be observed directly or integrally with certainty. Only their
consequences are, that is, changes that are fully accomplished.

These three properties impose very few restrictions on the set of systems that
can be abstracted and thus modelled by automata networks. These theoretical
objects are therefore generic models of a very wide variety of real systems.
It is therefore quite easy to understand the reasons that pushed scientists to
use them and to keep studying them in the context of ``fundamental
bioinformatics''.

Let us return to entities' characteristic "variable quantity" mentioned above.
Translating the quantity in terms of automata states, calls for a first
exercise of formalisation. This consists in choosing whether what interests us
in the variation of the quantity is of a Boolean, discrete or continuous
nature. As an illustration, let us take the example of genetic regulation and
choose the action of a gene as a variable quantity. If, in the action of this
gene, what interests us is its expression (and its non-expression), then the
state of the automaton chosen to model the gene should be Boolean. If it is
the different ways that this gene has of acting on the other elements of the
system that interests us, then we can choose to match an automaton state with
each way. This induces a discrete formalism which can obviously be encoded
without loss in a Boolean formalism, since an automaton with $k$ states can be
represented by $\log_{2}(k)$ Boolean automata. Finally, if we measure the
action of the gene by means of the concentration of proteins it produces,
continuous formalism turns out to be the most natural. On the other hand, it
brings a quantitative character. If this aspect is not desired, the tendency
will then be to approximate the protein concentration function at intervals in
order to fall back into a discrete, even Boolean framework by considering only
extreme concentrations for example. We can therefore grant different statuses
to the Boolean context depending on whether we see it as a direct modelling of
reality or as an approximation or encoding of an intrinsically continuous or
discrete modelling. Note that direct Boolean modelling is consistent with the
choice to focus on the state changes of the automata rather than on their
states themselves. By analogy to mechanics, if we see automata as internal
combustion engines, the interest relates to the fact that an engine is capable
of going from the ``off'' state to the ``on'' state (and vice versa) rather
than the amount of electricity supplied by the battery to start or on that
released by the candles to cause the explosion and initiate the movement.
Under this assumption, Boolean abstraction is necessary and sufficient.
Furthermore, in order to place ourselves in the context of modelling in
biology, it should be emphasised that the discourse of biologists is generally
imbued with syntactic elements of propositional logic. It is not uncommon to
hear sentences such as: ``in the absence of the repressor $\alpha$, the
$\beta$ gene is expressed'' or even ``if the products of the $\alpha$ and
$\beta$ genes form a complex, the latter promotes the expression of the
$\gamma$ gene while these genes tend to inhibit its expression when they are
in monomeric form''. This syntax also fits perfectly with a direct modelling
of reality in the Boolean formalism.

In addition, Boolean automata networks derive other interesting benefits from
their simplicity of definition. In particular, they provide a framework with
clearly defined contours, ideal for tackling fundamental problems around the
modelling of interacting entity systems. Given the variety of their nature and
the current state of our knowledge, the problems in question could not
currently benefit from significantly more elaborate frameworks. This would
inevitably lead to delaying the initial questions and to destructuring the
problem posed by paying attention to additional problems induced by the set of
parameters to be considered and not intrinsically included in the initial
problem. For these issues, on the contrary, Boolean automata networks offer
only what is essential and facilitate the manipulation of a minimal concept of
causality, which is rooted in the notion of state changes. Their merit
therefore lies in the reliability of the information they potentially provide,
delivered by their very high level of abstraction that also makes it possible
to obtain general laws that remain valid in more specific contexts. In other
words, it is crucial to understand that this simplicity of definition does not
necessarily make them ``simplistic'', and does not detract from their ability
to model complex phenomena that they allow to analyse qualitatively with a
surprising subtlety.

##  3 General definitions and notations

Informally, a Boolean automata network is comprised of abstract entities that
interact with each other. The abstract entities are called automata. Automata
have states which can take one of two values: either 0 (inactive) or 1
(active). The states of automata can change over the course of a discrete
time. They change under the influence of the states of other automata in the
network. This section aims to present the formalism of this model, giving the
main definitions and useful notations in the rest of the chapter.

###  3.1 Boolean automata networks

Let $\mathbb{B}=\\{\textsf{0},\textsf{{1}}\\}$ and $V=\\{0,\dots,n-1\\}$ be a
set of $n$ Boolean automata such that $\forall i\in V$, $x_{i}\in\mathbb{B}$
represents the _state_ of automaton $i$. A _configuration_ $x$ of a Boolean
automata network $f$ of size $n$ assigns a value of $\mathbb{B}$ to each of
the automata of $V$ and is classically noted as a vector
$x=(x_{0},\dots,x_{n-1})$ that is a vertex of the $n$-cube $\mathbb{B}^{n}$,
or as a binary word $x=x_{0}\dots x_{n-1}$. Formally, a _Boolean automata
network_ $f$ of size $n$ whose set of automata is $V$ is an ordered set of $n$
Boolean functions, such that $f=(f_{i}:\mathbb{B}^{n}\to\mathbb{B}\ |\ i\in
V)$. Given $i\in V$, $f_{i}$ is the _local transition function_ of automaton
$i$. It predetermines its evolution from any configuration $x$: if $i$ is
updated in configuration $x$ at time $t$, it goes from state $x_{i}(t)$ to
state $f_{i}(x(t))=x_{i}(t+1)$.

Let $s:\mathbb{B}\to\mbox{1l}$, with $\mbox{1l}=\\{-1,1\\}$, defined such that
$s(b)=b-(\neg b)$, the function allowing to convert a Boolean number into a
signed integer in 1l. In this chapter, we pay particular attention to the
state changes of automata, which leads us to introduce the following notations
for all $x$ in $\mathbb{B}^{n}$:

$\forall i\in V,\ \overline{x}^{\\{i\\}}=(x_{0},\dots,x_{i-1},\neg
x_{i},x_{i+1},\dots,x_{n-1})\text{.}$ $\forall W\subseteq V,\ \forall i\notin
W,\ \overline{x}^{W\cup\\{i\\}}=\overline{\overline{x}^{W}}^{\\{i\\}}\text{.}$

The _sign of an interaction_ from $i$ to $j$ in configuration $x$ is defined
by
$\text{sign}_{x}(i,j)=s(x_{i})\cdot(f_{j}(x)-f_{j}(\overline{x}^{\\{i\\}}))$.
The _effective interactions_ in $x$ belong to $E(x)=\\{(i,j)\in V\times V\ |\
\text{sign}_{x}(i,j)\neq 0\\}$. From there, we define the _interaction graph_
of $f$ as being the oriented graph $G=(V,E)$, where
$E=\bigcup_{x\in\mathbb{B}^{n}}E(x)$ is the set of interactions. In this
chapter, the Boolean automata networks discussed (see section 3.3) are special
in the sense that their interaction graphs are simple, namely that there can
only be one signed interaction $(i,j)\in E$. If it is signed positively (resp.
negatively), we say that it is activating (resp. inhibiting) and the state of
$j$ tends to mimic (resp. to oppose) that of $i$. In the following, the
interaction graphs will be signed for convenience of reading (see Figure 1).

$0$$1$$2$$+$$-$$-$$-$$-$$-$$+$$-$

$\left\\{\begin{array}[]{l}f_{0}(x)=x_{0}\lor\neg x_{1}\\\ f_{1}(x)=\neg
x_{0}\lor\neg x_{1}\lor x_{2}\\\ f_{2}(x)=\neg x_{0}\lor\neg x_{1}\lor\neg
x_{2}\\\ \end{array}\right.$

Figure 1: A Boolean automata network of size $3$: its interaction graph (on
the left), the ordered set of its local transition functions (on the right).

###  3.2 Updating modes and transition graphs

In order to determine the possible behaviours of a Boolean automata network,
it is essential to specify the way according to which the states of the
automata (or, abusing language, the automata) are updated over time. This
specification is what we call an updating mode. The most general point of view
is to consider all the possibilities. This amounts to seeing the evolution of
a network as a discrete dynamical system associated with a relation so that,
for each configuration, $2^{n}-1$ outgoing transitions are taken into account,
namely a transition for each subset of automata whose states can be updated.
More precisely, for all $W\neq\emptyset\subseteq V$, we define the update
function $F_{W}:\mathbb{B}^{n}\to\mathbb{B}^{n}$ such that:

$\forall x\in\mathbb{B}^{n},\forall i\in V,\
F_{W}(x)_{i}=\begin{cases}f_{i}(x)&\text{if }i\in W\text{,}\\\
x_{i}&\text{otherwise.}\end{cases}$

Thus, for the most general updating mode, called the _elementary updating
mode_ , the global behaviour of the network is given by the elementary
transition graph $\mathscr{G}_{e}=(\mathbb{B}^{n},T_{e})$, where
$T_{e}=\\{(x,F_{W}(x))\ |\ x\in\mathbb{B}^{n},W\neq\emptyset\subseteq V\\}$,
introduced in [Nou12b, Sen12].

The transitions $(x,F_{i}(x))$ that involve updating a single automaton $i\in
V$ are called _asynchronous transitions_. The transitions $(x,F_{W}(x))$, with
$|W|>1$, that induce the updating of several automata are called _synchronous
transitions_. The subgraph $\mathscr{G}_{a}=(\mathbb{B}^{n},T_{a})$ of
$\mathscr{G}_{e}$ whose set of arcs $T_{a}=\\{(x,F_{\\{i\\}}(x))\ |\
x\in\mathbb{B}^{n},i\in V\\}$ equals the set of asynchronous transitions of
network is called the _asynchronous transition graph_. This graph defines the
asynchronous dynamics of the network that corresponds to its dynamics when it
evolves according to the asynchronous updating mode, _i.e._ such that in each
configuration, only $n$ transitions are considered, one for each automaton.
This updating mode has been widely used in the studies of Thomas and his
collaborators [RMCT03, RRT08, RCB04, RC07, Ric10, Tho81, Tho91]. As an
illustration, the asynchronous transition graph of the network depicted in
Figure 1 is presented in Figure 2 (left). However, because it is the most
``natural'' (mathematically speaking) when only the local transition functions
are known, and because that it allows to give relevant insights through
transition graphs of smaller sizes, the _parallel updating mode_ occupies a
very important place in the literature on discrete dynamical systems in
general. When a network evolves in parallel, all of its automata update their
states at each time step. In other words, the parallel transition graph of a
network is $\mathscr{G}_{p}=(\mathbb{B}^{n},T_{p})$, where
$T_{p}=\\{(x,F_{V}(x)),x\in\mathbb{B}^{n}\\}$ is the subset of the perfectly
synchronous transitions of $T_{e}$. The parallel transition graph of the
network given in Figure 1 is presented in Figure 2 (right).

000001010011100101110111

000001010011100101110111

Figure 2: Two transition graphs of the Boolean automata network defined in
Figure 1. Left panel: its asynchronous transition graph where every
${\color[rgb]{.804,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{.804,0,0}\to}$
(resp.
${\color[rgb]{0,0,.804}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,.804}\to}$
and
${\color[rgb]{0,.545,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,.545,0}\to}$)
represents an update of automaton $0$ (resp. $1$ and $2$). Right panel: its
parallel transition graph. In each graph, stable configurations (a.k.a. fixed
points) are depicted in light gray while recurring configurations belonging to
stable oscillations (a.k.a. limit cycles) are depicted in dark gray.

Let us now specify notations and vocabulary relative to dynamical behaviours
of networks. Consider an arbitrary Boolean automata network $f$ of size $n$,
an updating mode $\mu$, the associated transition graph
$\mathscr{G}_{\mu}=(\mathbb{B}^{n},T_{\mu})$, and $x\in\mathbb{B}^{n}$ one of
its possible configurations. A _trajectory_ of $x$ is any path in
$\mathscr{G}_{\mu}$ that starts from $x$. A strongly connected component of
$\mathscr{G}_{\mu}$ which does not admit any outgoing transition is an
asymptotic behaviour of $(f,\mu)$, that we classically designate as an
_attractor_ of $(f,\mu)$. A configuration of $\mathbb{B}^{n}$ that belongs to
an attractor is a _recurring configuration_. Given an attractor, its _length_
is the number of recurring configurations that compose it. An attractor of
length $1$ (resp. of length strictly greater than $1$) is a _stable
configuration_ , a.k.a. a _fixed point_ (resp. a _stable oscillation_ , a.k.a.
a _limit cycle_) of $(f,\mu)$. If $\mu$ is a deterministic updating mode, such
as the parallel mode, attractors are simple cycles and the term _period_ is
preferred to refer to their length. Finally, we define the _convergence time
of a configuration_ $x$ as the length of its shortest trajectory which makes
it reach a recurring configuration. The _convergence time of the network_ is
the greatest convergence time of all its $2^{n}$ configurations. In the
transition graphs presented in this chapter, by convention, we associate the
light gray color with stable configurations and the dark gray color with
recurrent configurations belonging to stable oscillations. Thus, in Figure 2,
it can be seen that configuration 011 is stable for the asynchronous and
parallel updating modes. This is a direct consequence of the fact that a
stable configuration that is a fixed point of $f$ (implicitly evolving in
parallel) is preserved by every updating mode since it corresponds to the
vector of the local fixed points of the local transition functions. On the
other hand, we observe that the asynchronous transition graph admits a stable
oscillation of size $4$ while the parallel update mode admits a stable
oscillation of size $3$. This illustrates that stable oscillations are
generally not conserved when the updating mode is changed. This is a current
important field of study in the context of interaction networks and Boolean
automata networks.

###  3.3 Isolated cycles and tangential cycles

As mentioned in the introduction, we focus in this chapter on two sorts of
Boolean automata networks, namely, Boolean automata cycles and Boolean
automata double-cycles. The first are networks whose interaction graphs are
cycles. The second are networks whose interaction graphs are two cycles that
intersect tangentially. The founding results that lead us to develop ever more
research on these interaction patterns are presented in the following section.

A _Boolean automata cycle_ $\mathscr{C}_{n}$ is a Boolean automata network of
size $n$ whose interaction graph $G=(V,E)$ is a cycle, in the sense of graph
theory. $V$ is naturally assimilated to $\mathbb{Z}/n\mathbb{Z}$, so that
considering two automata $i$ and $j$ of $V$, $i+j$ represents $i+j\mod n$.
Thus, a Boolean automata cycle $\mathscr{C}_{n}$ is defined as an ordered set
of local transition functions of arity $1$ that are such that: $\forall i\in
V,\ f_{i}:\mathbb{B}^{n}\to\mathbb{B}$, and either $f_{i}(x)=x_{i-1}$ or
$f_{i}(x)=\neg x_{i-1}$. Note that there are two types of Boolean automata
cycle, positive and negative. A Boolean automata cycle is a _positive cycle_
$\mathscr{C}^{+}$ (resp. a _negative cycle_ $\mathscr{C}^{-}$) if it is
composed of an even number (resp. of an odd number) of inhibiting
interactions.

$\mathscr{C}_{\ell}^{+}$$\mathscr{C}_{r}^{+}$$0$$1$$\ell-1$$\ell$$n-1$$+$$+$$+$$+$$+$$+$$+$$+$$+$$+$$+$$+$

$\mathscr{C}_{\ell}^{-}$$\mathscr{C}_{r}^{+}$$0$$1$$\ell-1$$\ell$$n-1$$+$$+$$+$$+$$-$$+$$+$$+$$+$$+$$+$$+$

$\mathscr{C}_{\ell}^{-}$$\mathscr{C}_{r}^{-}$$0$$1$$\ell-1$$\ell$$n-1$$+$$+$$+$$+$$-$$+$$+$$+$$+$$+$$+$$-$

Figure 3: The three canonical Boolean automata double-cycles of size
$n=\ell+r-1$: the positive one (on the left), the mixed one (on the center),
and the negative one (on the right).

A _Boolean automata double-cycle_ $\mathscr{D}_{n}$, with $n=\ell+r-1$, is a
Boolean automata network of size $n$ composed of two Boolean automata cycles
$\mathscr{C}_{\ell}$ and $\mathscr{C}_{r}$ which tangentially intersect in one
automaton, automaton $0$. In the following, for reasons of clarity, we prefer
the notation $\mathscr{D}_{\ell,r}$. The set of automata of cycle
$\mathscr{C}_{\ell}$ is
$V^{\mathcal{L}}=\mathbb{Z}/\ell\mathbb{Z}=\\{0,...,\ell-1\\}$ and that of
cycle $\mathscr{C}_{r}$ is $V^{\mathcal{R}}={0}\cup\\{\ell-1+i\ |\ i\neq
0\in\mathbb{Z}/r\mathbb{Z}\\}$. In a Boolean automata double-cycle, by
definition, all the local transition functions are of arity $1$ except that of
automaton $0$ that is of arity $2$. In this work, we only consider locally
monotonous Boolean automata double-cycle, which induces that function $f_{0}$
is defined as $f_{0}(x)=f_{0}^{\mathcal{L}}(x)\diamond
f_{0}^{\mathcal{R}}(x)=x_{\ell-1}\diamond x_{n-1}$, where
$\diamond\in\\{\land,\lor\\}$. Note that the choice of operator $\diamond$
only changes the position of the configurations on the trajectories. In other
words, whatever the chosen updating mode, given two Boolean automata double-
cycle $\mathscr{D}_{\ell,r}$ and $\mathscr{D}^{\prime}_{\ell,r}$ such that
$f_{0}(x)=f_{\ell-1}(x)\land f_{n-1}(x)$ and
$f^{\prime}_{0}(x)=f^{\prime}_{\ell-1}(x)\lor f^{\prime}_{n-1}(x)$, their
respective transition graphs are identical up to an isomorphism on the
configurations. In addition, it is trivial to determine one from the other,
replacing the configurations with their opposites. Consequently, in the rest
of this chapter, to insist on this property, we will use without loss of
generality $f_{0}(x)=f_{l-1}(x)\lor f_{n-1}(x)$ (resp.
$f_{0}(x)=f_{\ell-1}(x)\land f_{n-1}(x)$) for Boolean automata double-cycles
evolving according to the parallel (resp. asynchronous) updating mode. Since
they are made up of two Boolean automata cycles, it is easy to see that there
are three distinct types of Boolean automata double-cycles. A positive Boolean
automata double-cycle is composed of two positive Boolean automata cycles and
is denoted by $\mathscr{D}_{\ell,r}^{+,+}$; a negative Boolean automata
double-cycle is composed of two negative Boolean automata cycles and is
denoted by $\mathscr{D}_{\ell,r}^{-,-}$; a mixed Boolean automata double-cycle
is composed of a negative Boolean automata cycle $\mathscr{C}^{-}$
tangentially intersected with a positive Boolean automata cycle
$\mathscr{C}^{+}$, and is denoted by $\mathscr{D}_{\ell,r}^{-,+}$.

Finally, in [Nou12b, Sen12], the authors have shown that the Boolean automata
cycles admit canonical representatives, and Boolean automata double-cycles too
by induction. The studies presented in the sequel focus on these canonical
representatives only. Indeed, canonicity means that two distinct Boolean
automata cycles or Boolean automata double-cycles of same sign and same size
that evolve following the same updating mode admit the same transition graph
up to an isomorphism on the configurations. A positive Boolean automata cycle
is said to be canonical when its interaction graph contains only activating
interactions. A negative Boolean automata cycle is canonical when its
interaction graph admits a single inhibiting interaction, represented by the
arc $(n-1,0)\in E$. The canonical Boolean automata double-cycles are the
canonical Boolean automata cycle compositions, depicted in Figure 3.

##  4 Seminal results on cycles

The works of Robert [Rob80] and Thomas [Tho81] have highlighted three
fundamental results that explain the primordial role that cycles play in the
behavioural diversity of interaction networks.

######  Theorem 1 ([Rob80, Rob86, Rob95]).

Let $f:\mathbb{B}^{n}\to\mathbb{B}^{n}$ be a Boolean automata network of size
$n$ and $G$ its associated interaction graph. If $G$ is an acyclic graph,
then:

  1. 1.

$f$ has a unique attractor that is a stable configuration, let us say $x$.

  2. 2.

$\mathscr{G}_{p}$ has a path of length at most $n$ from every configuration
$y$ to $x$.

  3. 3.

$\mathscr{G}_{a}$ is acyclic and has a a geodesic path from every
configuration $y$ to $x$.

This theorem is particularly interesting for two reasons. First, it is easy to
extend it to any kind of multi-valued automata networks
$g:\prod_{i=1}^{n}X_{i}\to\prod_{i=1}^{n}X_{i}$, where $X_{i}$ denotes the set
of possible states of automaton $i$, and to any kind of updating mode such
that every automaton is updated an infinite number of times over the course of
time (let us call such an updating mode a fair updating mode). Indeed, the
general idea of the proof rests on an induction on the depths of the automata
of the acyclic interaction graph that admits source automata. Source automata
are automata that are governed by constant local transition functions. They
inevitably become forever fixed once they are updated for the first time. In
an acyclic network, the fixity of source automata propagates. The states of
all the other automata progressively become fixed too as a result. The theorem
emphasizes that cycles are necessary conditions for interaction networks to
admit complex dynamics.

######  Theorem 2 ([RRT08, RC07, Tho81]).

Let $g:\prod_{i=1}^{n}X_{i}\to\prod_{i=1}^{n}X_{i}$ be an automata network and
$G$ its associated interaction graph. Under the asynchronous updating mode,
the presence of a positive cycle in $G$ is necessary for the dynamics of $g$
to admit several stable configurations.

This second theorem sheds light on the role of positive cycles on the ability
of interaction networks to stabilise in several ways. Although it was
originally stated and demonstrated under the asynchronous updating mode
hypothesis, this result has been shown to hold for any fair updating mode
[Nou12b, Sen12]. The general proof starts from the result of [RC07] and is
made by contradiction under the assumption of the absence of a positive cycle.
In this case, either the interaction graph is acyclic and Theorem 1 applies,
or it has at least one negative cycle and it is shown that such cycles,
whatever the updating mode, cannot remove the local instabilities on all
automata.

######  Theorem 3 ([Ric10, Tho81]).

Let $g:\prod_{i=1}^{n}X_{i}\to\prod_{i=1}^{n}X_{i}$ be an automata network and
$G$ its associated interaction graph. Under the asynchronous updating mode,
the presence of a negative cycle is necessary for the dynamics of $g$ to admit
a stable oscillation.

As for this third theorem, it turns out not to be general for all updating
modes. To be convinced, it suffices to compute the parallel transition graph
of an arbitrary positive Boolean automata cycle of size greater than $2$ and
to note that it admits at least one stable oscillation. Despite this lack of
generality, it should be noted that this theorem underlines the singular role
of negative cycles in connection with asymptotic dynamic oscillations, as will
be explained below.

Taken together, these three theorems, of which we can say that two of them are
laws insofar as their generality makes them sorts of meta-theorems of
interaction network theory, emphasise that the feedback cycles are the causes
of the dynamical complexity of networks. In other words, they effectively
constitute the sources of the behavioural diversity of networks and
consequently of the computational expressiveness of networks. This naturally
brings us to the following parts of this chapter, about major results
concerning the dynamical and combinatorial properties of Boolean automata
cycles and Boolean automata double-cycles. The results are illustrated with
examples. As discussed above, Robert's result highlighted feedback cycles as
kinds of complexity engines. Then, Thomas' results put forward the necessity
to distinguish feedback cycles depending on their (positive or negative)
nature to understand their influence. The results presented below about
Boolean automata double-cycles are a first step further, towards understanding
how cycle combinations operate and what their effects are.

##  5 Boolean automata cycle dynamics

In this section, we focus on Boolean automata cycles. In a first part, we
present in Theorem 4 the main results related to the dynamics of isolated
Boolean automata cycles when the latter evolve according to the parallel
updating mode. This theorem requires some preliminary definitions and
notations of number theory such as the Dirichlet convolution, the Möbius
function and the Euler's totient function. In a second part, we present the
results related to isolated Boolean automata cycles when the latter evolve
according to the asynchronous updating mode.

###  5.1 Parallel Boolean automata cycles

The first elements on the dynamics of Boolean automata cycles evolving
according to the parallel updating mode were introduced in [RMCT03]. The full
characterisation of their dynamics had to wait until [DNS12]. This
characterisation could be obtained thanks to an approach combining discrete
dynamical systems theory, enumerative and word combinatorics, particularly
appropriate to the nature of the mathematical objects in question.

####  5.1.1 Definitions and notations of pertinent quantities

To describe the results obtained, we give below definitions and notations.
First, given an attractor of (minimal) period $p$, we says that all the
multiples of $p$ are also periods of this attractor. So if
$x\in\mathbb{B}^{n}$ is a recurring configuration of an attractor of period
$p$, then $p$ is the period of $x$ and of any other configuration $y$ such
that there exists $t\in\mathbb{N}$ such that $y=F_{V}^{t}(x)$. We denote by
$\mathscr{X}(p)=\\{x\in\mathbb{B}^{n}\ |\ x=F_{V}^{p}(x)\\}$ the set of
recurring configurations of period $p$ and by $X(p)=|\mathscr{X}(p)|$ their
number. We define the smallest integer $\omega$ that is a period common to all
recurring configurations as the _order_ of the Boolean automata cycle, which
is said _to be reached_ when there exists an attractor of minimum period
$\omega$.

Let us consider the function $\textsf{\footnotesize one}:n\in\mathbb{N}\mapsto
1$ as well as the _Dirichlet convolution_ , denoted by
$\operatorname{\bigstar}$ [Apo76]. Given two functions $f$ and $g$,
$\operatorname{\bigstar}$ is the binary operator defined such that
$f\operatorname{\bigstar}g:n\in\mathbb{N}^{\ast}\mapsto\sum_{p|n}f(p)\cdot
g(n/p)$. The set of the arithmetic functions with point-to-point addition and
Dirichlet convolution is a commutative ring. The identity by the
multiplication of this ring is the function
$\delta:\mathbb{N}^{\ast}\to\mathbb{N}^{\ast}$, defined by $\delta(1)=1$ and
for all $n>1$, $\delta(n)=0$. The inverse of the function one for the
Dirichlet convolution is the Möbius function $\mu$, defined as:

$\mu:n\in\mathbb{N}^{\ast}\mapsto\begin{cases}0&\text{if }n\text{ is not
square-free,}\\\ 1&\text{if }n>0\text{ has an even number of prime
factors,}\\\ -1&\text{if }n>0\text{ has an odd number of prime
factors.}\end{cases}$

If $n=\prod_{i=0}^{k}p_{i}$, where the $p_{i}$s are the distinct prime numbers
taken in increasing order, then $\mu(n)=(-1)^{k}$. In our context, this
function is of interest through the Möbius inversion formula that is obtained
from $\textsf{\footnotesize one}\operatorname{\bigstar}\mu=\delta$, that is
satisfied by all the functions $f$ and $g$, and that is such that:
$g=f\operatorname{\bigstar}\textsf{\footnotesize one}\implies
f=g\operatorname{\bigstar}\mu$. In other words, we have:

$\forall n\in\mathbb{N}^{\ast},\ g(n)=\sum_{p|n}f(p)\ \implies\
f(n)=\sum_{p|n}g(p)\cdot\mu(n/p)\text{.}$

Another particularly useful function in the sequel is the _Euler's totient
function_ , denoted by $\operatorname{\phi}$. Given an integer
$n\in\mathbb{N}^{\ast}$, it associates the number of strictly positive
integers less than or equal to $n$ that are prime with $n$, such as:
$\operatorname{\phi}(n)=|\\{m\in\mathbb{N}^{\ast}\ |\ m\leq n\text{ and
}m\text{ is prime with }n\\}|$. Note that there is a relationship between the
Möbius function and the Euler's totient function. Indeed, as
$\operatorname{\phi}$ satisfies $\forall n\in\mathbb{N}^{\ast},\
n=\operatorname{\phi}\operatorname{\bigstar}\textsf{\footnotesize un}(n)$, it
respects
$\operatorname{\phi}=\mu\operatorname{\bigstar}\operatorname{\textsf{\footnotesize
id}}$, where $\operatorname{\textsf{\footnotesize
id}}:n\in\mathbb{N}^{\ast}\mapsto n$.

In terms of combinatorics, the asymptotic behaviour of an interaction network
can be described by means of four quantities [PW01] related to each other and
given below. Consider that $p$ is a divisor of the order $\omega$ of the
Boolean automata cycle studied and the function
$\operatorname{\textsf{\footnotesize inv}}:n\in\mathbb{N}^{\ast}\to 1/n$. We
then have the following quantities:

  * •

The _number_ $\texttt{X}(p)$ _of configurations of period $p$_ is
$\texttt{X}=\widetilde{\texttt{X}}\operatorname{\bigstar}\textsf{\footnotesize
one}$;

  * •

The _number_ $\widetilde{\texttt{X}}(p)$ _of configurations of minimal period
$p$_ is $\widetilde{\texttt{X}}=\texttt{X}\operatorname{\bigstar}\mu$;

  * •

The _number_ $\texttt{A}(p)=\widetilde{\texttt{X}}(p)/p$ _of attractors of
period $p$_ is $\texttt{A}=\operatorname{\textsf{\footnotesize
inv}}(\texttt{X}\operatorname{\bigstar}\mu)$;

  * •

The _total number_ $\texttt{T}(\omega)$ _of attractors_ is
$\texttt{T}=\texttt{A}\operatorname{\bigstar}\textsf{\footnotesize
one}=\operatorname{\textsf{\footnotesize
inv}}(\texttt{X}\operatorname{\bigstar}\operatorname{\phi})$.

The last two quantities correspond to well known formulas in the context of
Lyndon words and binary necklaces [BP07, GKP89, Rus03]: a Lyndon word $w$
being such that $w<v$ for all nonempty words $v$ such that $w=uv$ and $u$ is
nonempty; a binary necklace $w$ of length $n$ being a circular binary word
such that for all $i$ in $\mathbb{Z}$, $w_{i}=w_{i}\mod n$. In particular, the
penultimate defining A corresponds to the Witt formula counting the number of
Lyndon words; the last one defining T corresponds to the Burnside's orbit-
counting lemma. Note that the last formula is satisfied because
$\operatorname{\textsf{\footnotesize inv}}$ distributes over
$\operatorname{\bigstar}$. Finally, note that it suffices to calculate X to
obtain the others.

####  5.1.2 Results

The qualitative characterisation of the dynamics of Boolean automata cycles
can be summarised by the following theorem that presents in the form of a
table the set of all the quantities presented above. For reasons of space, the
details and the demonstrations related to these results are not presented
here. The reader can nevertheless find all the details in [DNS12, Nou12b,
Sen12].

000001010011100101110111

000001010011100101110111

Figure 4: Left panel: the parallel transition graph of positive canonical
Boolean automata cycle $\mathscr{C}_{3}^{+}$. Right panel: the parallel
transition graph of negative canonical Boolean automata cycle
$\mathscr{C}_{3}^{-}$.

######  Theorem 4 ([DNS12]).

The order $\omega$, the numbers $\texttt{X}(p)$ and
$\widetilde{\texttt{X}}(p)$ of configurations of (minimal) period $p$, where
$\texttt{X}(\omega)$ is the total number of recurring configurations, as well
as the number $\texttt{A}(p)$ of attractors of period $p$ and the total number
$\texttt{T}(\omega)$ of attractors of positive and negative Boolean automata
cycles are:

Positive cycles $\mathscr{C}^{+}_{n}$ Negative cycles $\mathscr{C}^{-}_{n}$
$\omega=n$ $\omega=2n$ $\texttt{X}^{+}(p)=2^{p}$
$\texttt{X}^{-}_{n}(p)=\neg(p|n)\cdot 2^{\frac{p}{2}}$
$\begin{array}[]{rcl}\widetilde{\texttt{X}}^{+}(p)&=&\underset{d|p}{\sum}\,\mu\left(\frac{p}{d}\right)\cdot
2^{d}\\\ &=&\texttt{OEIS A27375}(p)\end{array}$
$\begin{array}[]{rcl}\widetilde{\texttt{X}}^{-}_{n}(p)&=&\underset{k|p\text{
odd}}{\sum}\,\mu(k)\cdot 2^{\frac{p}{2k}}\end{array}$
$\begin{array}[]{rcl}\texttt{A}^{+}(p)&=&\frac{\widetilde{\texttt{X}}^{+}(p)}{p}\\\
&=&\texttt{OEIS A1037}(p)\end{array}$
$\begin{array}[]{rcl}\texttt{A}^{-}_{n}(p)&=&\frac{\widetilde{\texttt{X}}^{-}_{n}(p)}{p}\\\
&=&\texttt{OEIS A48}(\frac{p}{2})\end{array}$
$\begin{array}[]{rcl}\texttt{T}^{+}(\omega)&=&\frac{1}{n}\,\underset{d|n}{\sum}\,\operatorname{\phi}\left(\frac{n}{d}\right)\cdot
2^{d}\\\ &=&\texttt{OEIS A31}(n)\end{array}$
$\begin{array}[]{rcl}\texttt{T}^{-}(\omega)&=&\frac{1}{2n}\,\underset{k|2n\text{
odd}}{\sum}\,\operatorname{\phi}(k)\cdot 2^{\frac{n}{2k}}\\\ &=&\texttt{OEIS
A16}(n)\end{array}$ ,

where $\neg(p|n)$ is $0$ if $p$ divides $n$ and $1$ otherwise.

Among the particularly interesting properties of a parallel Boolean automata
cycle that emerge from this theorem, it should be noted that all of its
configurations are recurring, as illustrated in Figure 4, and that the total
number of attractors, for a given period or not, is exponential according to
its size $n$. Moreover, as a corollary, for the two types of cycles, the order
is reached, and positive cycles admit two stable configurations $x$ and
$\overline{x}^{V}$ (where $x$ is the configuration in which all the automata
are at state 0 for canonical Boolean automata cycles). Finally, another
important point is that this combinatorial study induces the complete
characterisation of the structure of the parallel transition graphs of both
positive and negative cycles.

It is also interesting to notice that these results go beyond the parallel
updating mode and extend to the block-sequential updating modes. Block-
sequential updating modes were introduced by Robert [Rob69]. They are
deterministic periodic updating modes defined by ordered partitions of $V$.
Given a period $p$, such an updating mode can be defined by a function
$\mu:V\to\mathbb{N}/p\mathbb{N}$. Indeed, in [GN10], the authors showed that
the dynamics of a Boolean automata cycle of size $n$ and sign $s\in{+,-}$
evolving according to a block-sequential updating mode is in essence
equivalent to that of a Boolean automata cycle of smaller size and same sign
evolving in parallel. The proof rests on substitutions of local transition
functions according to their execution over time. Hence, to understand the
dynamics of a Boolean automata cycle evolving according to a block-sequential
updating mode is a matter of understanding the dynamics in parallel of a
smaller Boolean automata cycle.

###  5.2 Asynchronous Boolean automata cycles

In combinatorial terms, the dynamics of asynchronous Boolean automata cycles
are much simpler than that of parallel Boolean automata cycles. It is in
[RMCT03] that we find the first characterisation of the attractors of
asynchronous Boolean automata cycles. The general idea of these results is
based on the concept of instability. In a given configuration of the network,
an automaton is said to be unstable if the application of its local transition
function would then make its state change. A configuration is unstable when it
has at least one unstable automaton. In particular, the authors showed that
asynchronism makes it possible to reduce the number of instabilities, until
there are none (resp. only one) left in the case of positive (resp. negative)
Boolean automata cycles. This property implies the existence of at least one
stable configuration in the positive case. In the negative case, it implies
the absence of stable configurations and thereby the existence of at least one
stable oscillation. Theorem 5 derives almost directly from this work. It is
illustrated by Figure 5.

000001010011100101110111

000001010011100101110111

Figure 5: Left panel: asynchronous transition graph of positive canonical
Boolean automata cycle $\mathscr{C}_{3}^{+}$. Right panel: asynchronous
transition graph of negative canonical Boolean automata cycle
$\mathscr{C}_{3}^{-}$. In both graphs, every
${\color[rgb]{.804,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{.804,0,0}\to}$
(resp.
${\color[rgb]{0,0,.804}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,.804}\to}$
and
${\color[rgb]{0,.545,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,.545,0}\to}$)
represents an update of automaton $0$ (resp. $1$ and $2$).

######  Theorem 5 ([RMCT03]).

A positive Boolean automata cycle $\mathscr{C}_{n}^{+}$ has two attractors
which are two stable configurations $x$ and $\overline{x}^{V}$. A negative
cycle $\mathscr{C}_{n}^{-}$ has a single attractor of length $2n$.

$\mathscr{D}_{2,2}^{+,+}$$0$$1$$2$$+$$+$$+$$+$

$\mathscr{D}_{1,3}^{+,+}$$0$$1$$2$$+$$+$$+$$+$

$\mathscr{D}_{2,2}^{-,+}$$0$$1$$2$$-$$+$$+$$+$

$\mathscr{D}_{1,3}^{-,+}$$0$$1$$2$$-$$+$$+$$+$

$\mathscr{D}_{2,2}^{-,-}$$0$$1$$2$$-$$+$$+$$-$

$\mathscr{D}_{1,3}^{-,-}$$0$$1$$2$$-$$+$$+$$-$

Figure 6: Top panel: Interaction graphs of two positive canonical Boolean
automata double-cycles. Middle panel: Interaction graphs of two mixed
canonical Boolean automata double-cycles. Bottom panel: Interaction graphs of
two negative canonical Boolean automata double-cycles. These six networks will
serve as examples in the sequel.

It is easy to see that the results stated in this theorem are strongly related
to those of Theorem 4. Indeed, first, the two stable configurations of
asynchronous positive cycles are identical to those of these same cycles in
parallel. And second, the unique stable oscillation of length $2n$ of a
negative cycle $\mathscr{C}_{n}^{-}$ under the asynchronous mode is identical
to that of period $\omega$ of parallel negative cycles. The two configurations
$x$ and $\overline{x}^{V}$ which are stable configurations in the case of
positive cycles, belong to the stable oscillations in the case of negative
cycles.

Finally, notice that this approach based on instabilities has been generalised
in [Nou12b, Sen12] to show the validity of Theorem 2 regardless of the
updating mode (see Section 4).

##  6 Boolean automata double-cycle dynamics

Now that the structural and combinatorial properties of the parallel and
asynchronous transition graphs of the Boolean automata cycles are established,
we present in this section those related to Boolean automata double-cycles.

###  6.1 Parallel Boolean automata double-cycles

In this section, we focus on Boolean automata double-cycles evolving according
to the parallel updating. The method used to obtain the results presented
follows the lines of method used for Boolean automata cycles.

####  6.1.1 Definitions and notations

Besides the four quantities $\texttt{X}(p)$, $\widetilde{\texttt{X}}(p)$,
$\texttt{A}(p)$ and $\texttt{T}(\omega)$ that we are going to use, we
introduce here other definitions and notations to characterise the dynamics of
Boolean automata double-cycles that are Boolean automata cycles tangentially
interconnected. In this sense, given any Boolean automata double-cycle
$\mathscr{D}_{\ell,r}^{s}$, where $s\in\\{(+,+),(-,+),(-,-)\\}$, two
quantities defined by means of $\ell$ and $r$ will be particularly useful,
$\Delta=\gcd(\ell,r)$ and $\Delta_{p}=\gcd(\Delta,p)$.

Moreover, the results call on combinatorics on words. So we introduce the
Lucas' and Perrin's sequences. These sequences will allow us to count the
number of recurring configurations. The Lucas' sequence $(\operatorname{{\tt
L}}(n))_{n\in\mathbb{N}^{\ast}}$ (OEIS A204) is defined by $\operatorname{{\tt
L}}(1)=1$, $\operatorname{{\tt L}}(2)=3$ and for all $n>2$,
$\operatorname{{\tt L}}(n)=\operatorname{{\tt L}}(n-1)+\operatorname{{\tt
L}}(n-2)$, and counts the number of binary necklaces of size $n$ without the
factor 00. The Perrin's sequence $(\operatorname{{\tt
P}}(n))_{n\in\mathbb{N}}$ (OEIS A1608) is defined by $\operatorname{{\tt
P}}(0)=3$, $\operatorname{{\tt P}}(1)=0$, $\operatorname{{\tt P}}(2)=2$ and
for all $n>2$, $\operatorname{{\tt P}}(n)=\operatorname{{\tt
P}}(n-2)+\operatorname{{\tt P}}(n-3)$, and counts the number of binary
necklaces of size $n$ without the factors 00 and 111.

####  6.1.2 Results

On the basis of the previous definitions and notations, Theorem 6 below gives
the qualitative characterisation of the dynamics of the different types of
Boolean automata double-cycles. It will be illustrated on six distinct Boolean
automata double-cycles depicted in Figure 6. The details of the proofs can be
found in [Nou12a, Nou12b, Sen12].

######  Theorem 6 ([Nou12a]).

The order $\omega$, the numbers $\texttt{X}(p)$ and
$\widetilde{\texttt{X}}(p)$ of configurations of (minimal) period $p$, where
$\texttt{X}(\omega)$ represents the total number of recurring configurations,
as well as the number $\texttt{A}(p)$ of asymptotic behaviours of period $p$,
and the total number $\texttt{T}(\omega)$ asymptotic behaviours of the
positive, mixed and negative Boolean automata double-cycles are:

Positive double-cycles $\mathscr{D}^{+,+}_{\ell,r}$ Mixed double-cycles
$\mathscr{D}^{-,+}_{\ell,r}$ Negative double-cycles
$\mathscr{D}^{-,-}_{\ell,r}$ $\omega=\Delta$ $\omega=r$
$\begin{cases}\frac{\ell+r}{2}&\text{if }\frac{\ell+r}{\Delta}=4\\\
\ell+r&\text{sinon}\end{cases}$ $\texttt{X}^{+}(p)$
$\texttt{X}^{-,+}_{\ell}(p)=\neg(p|\ell)\cdot\operatorname{{\tt
L}}(\frac{p}{\Delta_{p}})^{\Delta_{p}}$
$\texttt{X}^{-,-}_{\Delta}(p)=\neg(p|\Delta)\cdot\operatorname{{\tt
P}}(\frac{p}{\Delta_{p}})^{\Delta_{p}}$ $\widetilde{\texttt{X}}^{+}(p)$
$\widetilde{\texttt{X}}^{-,+}_{\ell}(p)=\underset{\begin{subarray}{c}d|p\\\
\neg(d|\ell)\end{subarray}}{\sum}\,\mu\left(\frac{p}{d}\right)\cdot\operatorname{{\tt
L}}(\frac{d}{\Delta_{d}})^{\Delta_{d}}$
$\widetilde{\texttt{X}}^{-,-}_{\Delta}(p)=\underset{\begin{subarray}{c}d|p\\\
\neg(d|\Delta)\end{subarray}}{\sum}\,\mu\left(\frac{p}{d}\right)\cdot\operatorname{{\tt
P}}(\frac{d}{\Delta_{d}})^{\Delta_{d}}$ $\texttt{A}^{+}(p)$
$\texttt{A}^{-,+}_{\ell}(p)=\frac{\widetilde{\texttt{X}}^{-,+}_{\ell}(p)}{p}$
$\texttt{A}^{-,-}_{\Delta}(p)=\frac{\widetilde{\texttt{X}}^{-,-}_{\Delta}(p)}{p}$
$\texttt{T}^{+}(\omega)$
$\texttt{T}^{-,+}_{\ell}(\omega)=\frac{1}{r}\underset{\begin{subarray}{c}d|r\\\
\neg(d|\ell)\end{subarray}}{\sum}\,\operatorname{\phi}\left(\frac{r}{d}\right)\cdot\operatorname{{\tt
L}}(\frac{d}{\Delta_{d}})^{\Delta_{d}}$
$\texttt{T}^{-,-}_{\Delta}(\omega)=\frac{1}{n}\underset{\begin{subarray}{c}d|n\\\
\neg(d|\Delta)\end{subarray}}{\sum}\,\operatorname{\phi}\left(\frac{n}{d}\right)\cdot\operatorname{{\tt
P}}(\frac{d}{\Delta_{d}})^{\Delta_{d}}$ ,

where $\neg(p|m)$ equals $0$ if $p$ divides $m$ and $1$ otherwise.

$\mathscr{D}_{2,2}^{+,+}$000001010011100101110111

$\mathscr{D}_{1,3}^{+,+}$000001010011100101110111

$\mathscr{D}_{2,2}^{-,+}$000001010011100101110111

$\mathscr{D}_{1,3}^{-,+}$000001010011100101110111

$\mathscr{D}_{2,2}^{-,-}$000001010011100101110111

$\mathscr{D}_{1,3}^{-,-}$000001010011100101110111

Figure 7: Parallel transition graphs of the canonical Boolean automata double-
cycles depicted in Figure 6, where $\diamond=\lor$.

Among other things (see Figure 6), it emerges from these results that _(i)_
positive Boolean automata double-cycles have two stable configurations $x$ and
$\overline{x}^{V}$ (with $x=(\textsf{0},...,\textsf{0})$ when they are
canonical) and that they have an asymptotic behaviour similar to positive
Boolean automata cycles of the same order, _(ii)_ mixed Boolean automata
double-cycles have a single stable configuration, and _(iii)_ negative Boolean
automata double-cycles have no stable configurations.

Also, we remark that, unlike Boolean automata cycles, the order of Boolean
automata double-cycles is not necessarily reached. Finally, this theorem
highlights again that, like Boolean automata cycles, Boolean automata double-
cycles admit an exponential number of attractors according to their size.
However, despite its exponential nature, the number of Boolean automata
double-cycle attractors is significantly smaller than that of Boolean automata
cycles. In other words, the intersections of cycles seem to participate
strongly in the reduction of asymptotic degrees of freedom of interaction
networks. Based on this idea, studies have been conducted to compare
$\texttt{T}^{+}(n)$ and $\texttt{T}^{-}(2n)$ of Boolean automata cycles with
quantities $\texttt{T}^{+}(\Delta)$, $\texttt{T}^{-,+}_{\ell}(r)$ and
$\texttt{T}^{-,-}_{\Delta}(\ell+r)$ of Boolean automata double-cycles.

Consider a network $f$ of order $\omega$, so that $f=\mathscr{C}_{n}^{s}$ or
$f=\mathscr{D}_{\ ell,r}^{s,s^{\prime}}$, where $s,s^{\prime}\in\\{+,-\\}$.
Let $p$ be a divisor of $\omega$. Also note
$\texttt{Q}\in\\{\texttt{X},\widetilde{\texttt{X}},\texttt{A},\texttt{T}\\}$
one of the four quantities analysed. It has been demonstrated in [Nou12b,
Sen12] that $\texttt{Q}^{+,+}_{\ell,r}(p)=\texttt{Q}^{+}(p)$,
$\texttt{X}^{-,+}_{\ell,r}(p)\leq\texttt{X}^{+}(p)$, $\texttt{X}^{-,-}_{\
ell,r}(p)\leq\texttt{X}^{+}(p)$ and
$\texttt{Q}_{\ell,\ell}^{s,s}(p)=\texttt{Q}^{s}_{\ell}(p)$.

However, the number of recurring configurations of a Boolean automata double-
cycle, $\texttt{X}_{\ell,r}^{s,s}(p)$ has been bounded more finely as a
function of $\texttt{X}_{n}^{+}(p)$ and $\texttt{X}_{n}^{-}(p)$, based on the
previous results as well as on the relation of the Lucas sequence with the
golden ratio [Rib96], denoted by $\operatorname{\varrho}=(1+\sqrt{5})/2$ (root
of $x^{2}-x-1=0$) and that of the Perrin sequence with the plastic number
[van60], denoted by
$\operatorname{\xi}=\sqrt[3]{\frac{1}{2}+\frac{1}{6}\sqrt{\frac{23}{3}}}+\sqrt[3]{\frac{1}{2}-\frac{1}{6}\sqrt{\frac{23}{3}}}$
(root of $x^{3}-x-1=0$). The bounds found led to Theorem 7 that concludes this
part by highlighting that a vast majority of recurring configurations have the
greatest minimum period possible.

######  Theorem 7 ([Nou12b]).

Let $f$ be a Boolean automata network of order $\omega$. If $f$ is a Boolean
automata cycle or a Boolean automata double-cycle such as $f$ is neither
$\mathscr{D}_{5,1}^{-,-}$ nor $\mathscr{D}_{1,5}^{-,-}$, then its total number
of attractors $\texttt{T}(\omega)$ is bounded by its total number of recurring
configurations $\texttt{X}(\omega)$ so that:

$\frac{\texttt{X}(\omega)}{\omega}\leq\texttt{T}(\omega)\leq
2\cdot\frac{\texttt{X}(\omega)}{\omega}\text{,}$

which means that the attractor periods of $f$ are very large:

$\sum_{p|\omega}p\cdot\frac{\texttt{A}(p)}{\texttt{T}(\omega)}=\frac{\texttt{X}(\omega)}{\texttt{T}(\omega)}\geq\frac{\omega}{2}\text{.}$

To end this section dedicated to parallel Boolean automata double-cycles,
notice that all the results presented here extend naturally to any tangential
double-cycles, namely two cycles that admit several automata in common such
that these common automata are organised into an isolated path so that each of
them have a local transition function of arity $1$ except the first one for
which the arity is $2$. The proof is simple and rests on an induction
consisting in transforming each tangential automaton whose local transition
function arity is $1$ (by following the isolated path in reverse direction)
into two copies, one in the left cycle and one in the right cycle. Following
this reasoning, it is easy to see that such a tangential double-cycle is
equivalent to a Boolean automata double-cycle whose cycles are of bigger sizes
and same signs.

Moreover, notice that both Boolean automata cycles and Boolean automata
double-cycles admit an exponential number of attractors. This is quite
unrealistic if we view these objects as models of genetic regulation networks.
Indeed, ``real'' genetic regulation networks seem to have a number of
asymptotic behaviours (cellular types, biological rhythms…) that is polynomial
(perhaps linear) according to the number of their genes. Nevertheless, it is
important to see that the results obtained show that the number of attractors
of Boolean automata double-cycles is drastically smaller than that of Boolean
automata cycles. Actually, we think that the polynomial characteristics of the
number of attractors of real regulation systems comes from the entanglement of
cycles. More precisely, without formalising it, we conjecture that the more
there are entangled cycles, the less there are local and global instabilities,
the less there are attractors (simply because adding intersections adds
dynamical constraints), and thus the less automata networks are sensitive to
synchronism.

###  6.2 Asynchronous Boolean automata double-cycles

The last part of this synthesis is devoted to the dynamics of asynchronous
Boolean automata double-cycles. It presents the characterisation established
in [MNR+15]. It is the counterpart of the study of the dynamics of Boolean
automata double-cycles under the parallel updating mode. The study of the
asynchronous case takes a new approach. It formalises long sequences of
updates by way of algorithmic descriptions. This approach allows an elegant
and more detailed description of the dynamics of feedbacks in interaction
networks than the previous works. In particular it facilitates the study of
convergence times.

####  6.2.1 Definitions and notations

For the sake of clarity, let us first recall that the study surveyed here
focuses on canonical Boolean automata double-cycles.

##### _States and configurations_

Here, we will use the classical notation $V=\\{0,\dots,n-1\\}$ for
representing the automata of a network of size $n$ and its congruence
$V\equiv\\{c=c_{0},c_{1},dots,c_{n-1}\\}$. A configuration
$x\in\mathbb{B}^{n}$ is seen as a vector of two binary words. The first symbol
of these two words represents $x_{c}\equiv x_{0}$. The null configuration is
therefore denoted by $(\textsf{0}^{\ell},\textsf{0}^{r})$. Furthermore, we
denote by $x^{\ell}$ (resp. $x^{r}$) the projection of $x$ on the Boolean
automata cycle $\mathscr{C}_{\ell}$ (resp. $\mathscr{C}_{r}$). This way,
$x=(x^{\ell},x^{r})$, and in configuration $x$, the state of automaton
$c_{i}^{\ell}$ is $x_{i}^{\ell}$. Notice that $x_{0}=x_{0}^{\ell}=x_{0}^{r}$
since the three notations represent the state of automaton $c$ in $x$.

##### _Expressiveness measure_

Let $x$ be a configuration of a Boolean automata cycle $\mathscr{C}_{n}$. Its
_expressiveness_ is the number of factors 01 that compose it, namely $|\\{i\
|\ 0\leq i\leq n-1,x_{i}=\textsf{0}\text{ and }x_{i+1\mod
n}=\textsf{{1}}\\}|$. The expressiveness of a configuration $x$ of a Boolean
automata double-cycle is the sum of the expressiveness of $x^{\ell}$ and
$x^{r}$. From this definition follows that, if $\ell$ and $r$ are even, the
least expressive configurations are $(\textsf{0}^{\ell},\textsf{0}^{r})$ and
$(\textsf{{1}}^{\ell},\textsf{{1}}^{r})$, and that the most expressive ones
are
$((\textsf{0}\textsf{{1}})^{\frac{\ell}{2}},(\textsf{0}\textsf{{1}})^{\frac{r}{2}})$
and
$((\textsf{{1}}\textsf{0})^{\frac{\ell}{2}},(\textsf{{1}}\textsf{0})^{\frac{r}{2}})$.

##### _Elementary instructions_

Network trajectories can be very long. To study them, we need a way to
efficiently describe the sequence of automata updates that they execute. Our
human minds must be able to understand from the description, what is the
effect of the trajectory on the network, what changes does the network undergo
along the trajectory. To do so, we proposed to view these sequences as
instructions that make it easier to capture their effect on configurations.
Let us therefore consider:

  * •

a Boolean automata double-cycle $\mathscr{D}_{n}$,

  * •

one of the Boolean automata cycles of $\mathscr{D}_{n}$, namely $\mathscr{C}$,
whose size is noted $\texttt{\small size}(\mathscr{C})$,

  * •

the current configuration $x$ of $\mathscr{C}$, and,

  * •

two automata of $\mathscr{C}$ distinct from $c$, namely $c_{i}$ and $c_{j}$,
such that $i<j$.

With these notations, the following seven basic instructions are defined:

  1. 1.

/* update of automaton $c$ */
sync: $x_{c}\leftarrow f_{c}(x)$

     * Instruction sync is the only instruction that updates automaton $c$ and where both Boolean automata cycles interact with each other. This (key)-instruction will always be called when $c$ can change its state. This instruction can be used either to set $c$ at a desired state or to increase the expressiveness from a configuration. Furthermore, it is the only way to switch a 111 (resp. 000) pattern into a 101 (resp. 010) pattern and, thus, to increase the expressiveness.

  2. 2.

/* update of automaton $c_{i}$ */
$\texttt{\small update}(c_{i})$: $x_{c_{i}}\leftarrow f_{c_{i}}(x)$

     * Instruction update updates an automaton distinct from $c$.

  3. 3.

/* incremental updates */
$\texttt{\small incUp}(\mathscr{C},i,j)$: for $k=i$ upto $j$ do
$\texttt{\small update}(c_{k})$

     * Instruction incUp updates consecutive automata in increasing order. In fact, incUp propagates the state of $c_{i-1}$ along $\mathscr{C}$. Notice that if $j<i$ then no automata are updated. Moreover, since $i\neq 0$ and $j\neq 0$, $c$ cannot be updated with incUp. This instruction admits the following property. Let $x^{\prime}$ be the result of the execution of $\texttt{\small incUp}(\mathscr{C},i,j)$ on configuration $x$. Then $\forall k\in\\{i,\ldots,j\\},\ x^{\prime}_{k}=x_{i-1}$ and $\forall k\notin\\{i,\ldots,j\\},\ x^{\prime}_{k}=x_{k}$.

  4. 4.

/* incremental propagation of $x_{c}$ */
$\texttt{\small erase}(\mathscr{C})$: $\texttt{\small
incUp}(\mathscr{C},1,\texttt{\small size}(\mathscr{C})-1)$

     * Instruction erase is a particular case of incUp. It propagates the state of $c_{0}$ along $\mathscr{C}$. As a consequence, using erase on $\mathscr{C}$ decreases its expressiveness to $0$, and thus, is really efficient to reach quickly the least expressive configuration. This instruction admits the following property. Let $x^{\prime}$ be the result of applying $\texttt{\small erase}(\mathscr{C})$ on configuration $x$. Then we have: $\forall k\in\\{0,\ldots,\texttt{\small size}(\mathscr{C})-1\\},\ x^{\prime}_{k}=x_{0}$.

  5. 5.

/* incremental propagation of $x_{c}$ with no loss of expressiveness */
$\texttt{\small expand}(\mathscr{C})$: $\texttt{\small
incUp}(\mathscr{C},1,\kappa-1\in\mathbb{N})$
where $\kappa=\underset{1\leq k\leq\texttt{\small
size}(\mathscr{C}-1)}{\min}\left\\{k\ |\ \begin{cases}(x_{k}=0)\text{ and
}(x_{k+1\mod\texttt{\small size}(\mathscr{C})}=1)&\text{if }x_{c}=1\\\
(x_{k}=1)\text{ and }(x_{k+1\mod\texttt{\small size}(\mathscr{C})}=0)&\text{if
}x_{c}=0\end{cases}\right\\}$.

     * Instruction expand is another particular case of incUp that aims at propagating the state of $c_{0}$ along $\mathscr{C}$ while neither 01 nor 10 patterns are destroyed, which avoids decreasing the expressiveness of $\mathscr{C}$.

  6. 6.

/* decremental updates */
$\texttt{\small decUp}(\mathscr{C},i,j)$: for $k=j$ downto $i$ do
$\texttt{\small update}(c_{k})$

     * Instruction decUp is the converse of instruction incUp, and updates consecutive automata in decreasing order. Once $\texttt{\small decUp}(\mathscr{C},i,j)$ executed, the information of $c_{j}$ is lost and that of $c_{i-1}$ is possessed by both $c_{i-1}$ and $c_{i}$. In fact, decUp aims at shifting partially a Boolean automata cycle section. As for incUp, if $j<i$ then no automata are updated and $c$ cannot be updated with decUp. This instruction admits the following property. Let $x^{\prime}$ the result of the execution of $\texttt{\small decUp}(\mathscr{C},i,j)$ on $x$. Then $\forall k\in\\{i,\ldots,j\\},\ x^{\prime}_{k}=x_{k-1}$ and $\forall k\notin\\{i,\ldots,j\\},\ x^{\prime}_{k}=x_{k}$.

  7. 7.

/* complete decremental update (except $c$) */
$\texttt{\small shift}(\mathscr{C})$: $\texttt{\small
decUp}(\mathscr{C},1,\texttt{\small size}(\mathscr{C})-1)$

     * Instruction shift is a particular case of instruction decUp. Once executed, every automaton of $\mathscr{C}$ takes the state of its predecessor, except $c$ whose state does not change. Automaton $c_{\texttt{\small size}(\mathscr{C}-1)}$ excluded, all the information contained along $\mathscr{C}$ is kept safe. This instruction is useful to propagate information along a Boolean automata cycle without loosing too much expressiveness (at most one 01 pattern is destroyed).

####  6.2.2 Results

##### _More complex instructions_

Let $x$ be a configuration of a Boolean automata double-cycle $\mathscr{D}$.
Let us consider an algorithm composed of instructions defining an update
sequence $\texttt{\small sequence}(x)$ from $x$. In every algorithm that
follows, Boolean automata double-cycle $\mathscr{D}$ is always considered as a
global variable and is not mentioned. Abusing language, $\texttt{\small
sequence}(x)$ represents the sequence as well as the configuration resulting
from its execution.

For the purpose of the study, we introduce three other more complex sequences
in Table 1. In addition, Lemma 1 below shows that the copy instruction allows
to transform $x$ into another configuration $x^{\prime}$ if $x$ is
sufficiently expressive.

$\texttt{\small copy\\_c}(x,x^{\prime},\mathscr{C}_{m})$ 01\.
$\eta\leftarrow\texttt{\small size}(\mathscr{C}_{m})$; 02\. if
($x^{m}_{\eta-1}=x^{m}_{\eta-2}\textbf{ and }x^{m}_{\eta-1}\neq x^{\prime
m}_{\eta-1}$) then 03\. $j\leftarrow\max\\{k\ |\ k<\eta-1\text{ and
}x^{m}_{k}\neq x^{\prime m}_{k}\\}$; 04\. else 05\. $j\leftarrow\eta$; 06\. fi
07\. for ($k=\eta-1$) downto ($j+1$) do 08\. $\texttt{\small
update}(c^{m}_{k-1})$; 09\. $\texttt{\small update}(c^{m}_{k})$; 10\. od 11\.
for ($k=j-1$) downto ($1$) do 12\. if ($x^{m}_{k}\neq x^{\prime m}_{k}$) then
13\. $\texttt{\small update}(c^{m}_{k})$; 14\. fi 15\. od $\texttt{\small
copy}(x,x^{\prime})$ 01\. $\texttt{\small
copy\\_c}(x,x^{\prime},\mathscr{C}_{\ell})$; 02\. $\texttt{\small
copy\\_c}(x,x^{\prime},\mathscr{C}_{r})$; $\texttt{\small
copy\\_p}(x,x^{\prime})$ 01\. if ($x_{0}\neq x^{\prime}_{0}$) then 02\.
$\texttt{\small shift}(\mathscr{C}_{\ell})$; 03\. $\texttt{\small
shift}(\mathscr{C}_{r})$; 04\. sync; 05\. fi 06\. $\texttt{\small
copy}(x,x^{\prime})$;

Table 1: The update sequences copy_c, copy and copy_p.

######  Lemma 1 ([MNR+15]).

Let $\mathscr{D}$ be a Boolean automata double-cycle and let $x$ and
$x^{\prime}$ be two of its configurations such that $x_{0}=x^{\prime}_{0}$.
If, for all $m\in\\{\ell,r\\}$, one of the following properties holds for $x$:

  1. 1.

$\forall i\in\\{1,\ldots,\texttt{\small size}(\mathscr{C}_{m})-1\\},\
x^{m}_{i}\neq x^{m}_{i-1}$,

  2. 2.

$\forall i\in\\{1,\ldots,\texttt{\small size}(\mathscr{C}_{m})-2\\},\
x^{m}_{i}\neq x^{m}_{i-1}\text{ and }x^{m}_{\texttt{\small
size}(\mathscr{C}_{m})-1}=x^{\prime m}_{\texttt{\small
size}(\mathscr{C}_{m})-1}$,

  3. 3.

$\forall i\in\\{1,\ldots,\texttt{\small size}(\mathscr{C}_{m})-2\\},\
x^{m}_{i}\neq x^{m}_{i-1}\text{ and }\exists p\in\\{1,\ldots,\texttt{\small
size}(\mathscr{C}_{m})-2\\},x^{m}_{p}\neq x^{\prime m}_{p}$,

then $\texttt{\small copy}(x,x^{\prime})=x^{\prime}$ and this sequence
executes at most $2(\ell+r-6)$ updates.

This lemma gives strong insights about the expressive power of instructions
and sequences to reveal possible trajectories between configurations. Now let
us focus on the dynamical behaviour of Boolean automata double-cycles, from a
general point of view.

##### _Positive Boolean automata double-cycles_

In section 6.1, we have seen that positive Boolean automata double-cycles
behave like positive Boolean automata cycles, namely they have two stable
configurations among their attractors. In the asynchronous case, these two
stable configurations are the only attractors. The general idea of the
demonstration is based on canonical positive Boolean automata double-cycles
and establishes that the two sequences fix0 and fix1 given in Table 2 allow to
transform any configuration with at least one automaton in state 0 into
configuration $(\textsf{0}^{\ell},\textsf{0}^{r})$, and any configuration with
at least one automaton in state 1 in each of its Boolean automata cycles into
configuration $(\textsf{{1}}^{\ell},\textsf{{1}}^{r})$. This result is
illustrated at the top of Figure 8, and is summarised in Theorem 8 below.

$\texttt{\small fix0}(x)$ 01\. if ($x_{0}=\textsf{{1}}$) then 02\.
$i\leftarrow\min\\{k\ |\ x^{\ell}_{k}=\textsf{0}\\}$; 03\. $\texttt{\small
incUp}(\mathscr{C}_{\ell},i+1,\ell-1)$; 04\. sync; 05\. fi 06\.
$\texttt{\small erase}(\mathscr{C}_{\ell})$; 07\. $\texttt{\small
erase}(\mathscr{C}_{r})$; $\texttt{\small fix1}(x)$ 01\. if
($x_{0}=\textsf{0}$) then 02\. $i\leftarrow\min\\{k\ |\
x^{\ell}_{k}=\textsf{{1}}\\}$; 03\. $\texttt{\small
incUp}(\mathscr{C}_{\ell},i+1,\ell-1)$; 04\. $j\leftarrow\min\\{k\ |\
x^{r}_{k}=\textsf{{1}}\\}$; 05\. $\texttt{\small
incUp}(\mathscr{C}_{r},j+1,r-1)$; 06\. sync; 07\. fi 08\. $\texttt{\small
erase}(\mathscr{C}_{\ell})$; 09\. $\texttt{\small erase}(\mathscr{C}_{r})$;

Table 2: The update sequences fix0 and fix1.

######  Theorem 8 ([MNR+15]).

Let $\mathscr{D}^{+,+}$ be a canonical positive Boolean automata double-cycle
where $\diamond=\land$ and $x$ one of its unstable configurations. If $x$
admits one automaton in state $0$, then $\texttt{\small
fix0}(x)=(\textsf{0}^{\ell},\textsf{0}^{r})$. Moreover, if in configuration
$x$, there is one automaton in state 1 in each Boolean automata cycle, then
$\texttt{\small fix1}(x)=(\textsf{{1}}^{\ell},\textsf{{1}}^{r})$. The
convergence time of $\mathscr{D}^{+,+}$ is at most $2(\ell+r)-5$.

##### _Mixed Boolean automata double-cycles_

For mixed asynchronous Boolean automata double-cycles, as for positive ones,
asynchronism allows to eliminate all local instabilities. Thus, contrary to
parallel Boolean automata double-cycles, asynchronous Boolean automata double-
cycles have only one attractor that is a stable configuration. In the
canonical case, this is evidenced by the simp sequence given in Table 3 that
provides a way to converge towards this stable configuration from any initial
configuration $x$, by reducing progressively its expressiveness. This result
is illustrated in Figure 8 (middle) and is formalised by Theorem 9 below.

######  Theorem 9 ([MNR+15]).

Let $\mathscr{D}^{-,+}$ be a canonical mixed Boolean automata double-cycle,
where $\diamond=\land$. For any of its configuration $x$, $\texttt{\small
simp}(x)=(\textsf{0}^{\ell},\textsf{0}^{r})$ holds. The convergence time of
$\mathscr{D}^{-,+}$ is at most $2\ell+r-2$.

##### _Negative Boolean automata double-cycles_

Here, we distinguish between (1) _even_ negative Boolean automata double-
cycles and (2) _odd_ negative Boolean automata double-cycles. The first ones
are defined as having two even-sized Boolean automata cycles, the second ones
as having at least one odd-sized Boolean automata cycle.

Even negative Boolean automata double-cycles admit a single attractor. This
attractor is a stable oscillation of length $2^{\ell+r-1}$. This means that
all the configurations are recurring and consequently the convergence time is
null. All configurations are reachable. However this result also means that
configurations of maximal expressiveness are hard to reach: the number of
updates to reach them is quadratic according to the size of the Boolean
automata double-cycle. The general idea of the proof follows the following
three points:

  * •

Any configuration can reach the less expressive one
$(\textsf{0}^{\ell},\textsf{0}^{r})$ in linear time. (P1)

  * •

Configuration $(\textsf{0}^{\ell},\textsf{0}^{r})$ can reach the highest
expressive one
$((\textsf{{1}}\textsf{0})^{\frac{\ell}{2}},(\textsf{{1}}\textsf{0})^{\frac{r}{2}})$
in quadratic time. (P2)

  * •

Any configuration can be reached from
$((\textsf{{1}}\textsf{0})^{\frac{\ell}{2}},(\textsf{{1}}\textsf{0})^{\frac{r}{2}})$
in linear time. (P3)

$\texttt{\small simp}(x)$ 01\. if ($x_{0}=\textsf{{1}}$) then 02\.
$\texttt{\small erase}(\mathscr{C}_{\ell})$; 03\. sync; 04\. fi 05\.
$\texttt{\small erase}(\mathscr{C}_{\ell})$; 06\. $\texttt{\small
erase}(\mathscr{C}_{r})$; $\texttt{\small comp1}(x)$ 01\. for ($i=1$) upto
($\ell-1$) do 02\. sync; 03\. $\texttt{\small expand}(\mathscr{C}_{\ell})$;
04\. $\texttt{\small erase}(\mathscr{C}_{r})$; 05\. od $\texttt{\small
comp2}(x)$ 01\. if ($x^{r}=\textsf{{1}}^{r}$) then 02\. sync; 03\.
$\texttt{\small erase}(\mathscr{C}_{r})$; 04\. fi 05\. sync; 06\.
$\texttt{\small expand}(\mathscr{C}_{r})$; 07\. for ($i=1$) upto ($r-2$) do
08\. $\texttt{\small shift}(\mathscr{C}_{\ell})$; 09\. sync; 10\.
$\texttt{\small expand}(\mathscr{C}_{r})$; 11\. od

Table 3: The update sequences simp, comp1 and comp2.

Consider P1. It is easy to see that the sequence simp remains effective for
reaching $(\textsf{0}^{\ell},\textsf{0}^{r})$, which is formalised by Lemma 2
below.

######  Lemma 2 ([MNR+15]).

For any configuration $x$ of $\mathscr{D}_{\ell,r}^{-,-}$, $\texttt{\small
simp}(x)=(\textsf{0}^{\ell},\textsf{0}^{r})$ and executes at most $2\ell+r-2$
updates.

$\mathscr{D}_{2,2}^{+,+}$000001010011100101110111

$\mathscr{D}_{1,3}^{+,+}$000001010011100101110111

$\mathscr{D}_{2,2}^{-,+}$000001010011100101110111

$\mathscr{D}_{1,3}^{-,+}$000001010011100101110111

$\mathscr{D}_{2,2}^{-,-}$000001010011100101110111

$\mathscr{D}_{1,3}^{-,-}$000001010011100101110111

Figure 8: Asynchronous transition graphs of the canonical Boolean automata
double-cycles depicted in Figure 6, where $\diamond=\land$ and where every
${\color[rgb]{.804,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{.804,0,0}\to}$
(resp.
${\color[rgb]{0,0,.804}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,.804}\to}$
and
${\color[rgb]{0,.545,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,.545,0}\to}$)
represents an update of automaton $0$ (resp. $1$ and $2$).

Now, consider P2. Implicitly, P2 requires increasing the expressiveness of
$(\textsf{0}^{\ell},\textsf{0}^{r})$ by successive updates, and finding a
trajectory that reaches
$((\textsf{{1}}\textsf{0})^{\frac{\ell}{2}},(\textsf{{1}}\textsf{0})^{\frac{r}{2}})$.
To do so, we proceed in two stages. First, we increase the expressiveness of
$\mathscr{C}_{\ell}$ using comp1 (see Lemma 3). Then, we increase the
expressiveness of $\mathscr{C}_{r}$. This second stage is carried out without
reducing the expressiveness of $\mathscr{C}_{\ell}$ by using comp2 (see Lemma
4). The expected result follows from the composition $\texttt{\small
comp}=\texttt{\small comp2}\circ\texttt{\small comp1}$. It is formalised in
Lemma 5.

######  Lemma 3 ([MNR+15]).

In an even negative Boolean automata double-cycle
$\mathscr{D}_{\ell,r}^{-,-}$, sequence

$\texttt{\small comp1}((\textsf{0}^{\ell},\textsf{0}^{r}))$

leads to configuration
$((\textsf{{1}}\textsf{0})^{\frac{\ell}{2}},\textsf{{1}}^{r})$ and executes at
most $(\ell-1)(\ell+r-2)$ updates.

######  Lemma 4 ([MNR+15]).

In an even negative Boolean automata double-cycle
$\mathscr{D}_{\ell,r}^{-,-}$, sequence

$\texttt{\small
comp2}(((\textsf{{1}}\textsf{0})^{\frac{\ell}{2}},\textsf{{1}}^{r}))$

leads to configuration
$((\textsf{{1}}\textsf{0})^{\frac{\ell}{2}},(\textsf{{1}}\textsf{0})^{\frac{r}{2}})$
and executes at most $(r-2)(\ell+r-2)+(2r-1)$ updates.

######  Lemma 5 ([MNR+15]).

In an even negative Boolean automata double-cycle
$\mathscr{D}_{\ell,r}^{-,-}$, sequence

$\texttt{\small comp}((\textsf{0}^{\ell},\textsf{0}^{r}))$

leads to configuration
$((\textsf{{1}}\textsf{0})^{\frac{\ell}{2}},(\textsf{{1}}\textsf{0})^{\frac{r}{2}})$
and executes at most $(\ell+r)^{2}-5(\ell-1)-3r$ updates.

P3 is developed in Lemma 6 that uses the copy_p sequence (see Table 1).

######  Lemma 6 ([MNR+15]).

In an even negative Boolean automata double-cycle
$\mathscr{D}_{\ell,r}^{-,-}$, for any configuration $x^{\prime}$, sequence

$\texttt{\small
copy\\_p}(((\textsf{{1}}\textsf{0})^{\frac{\ell}{2}},(\textsf{{1}}\textsf{0})^{\frac{r}{2}}),x^{\prime})$

transforms configuration
$((\textsf{{1}}\textsf{0})^{\frac{\ell}{2}},(\textsf{{1}}\textsf{0})^{\frac{r}{2}})$
into $x^{\prime}$ in at most $3(\ell+r-4)-1$ updates.

Starting from Lemmas 2 to 6, whatever the configurations $x$ and $x^{\prime}$,
the composition

$\texttt{\small copy\\_p}(\texttt{\small comp}(\texttt{\small
simp}(x)),x^{\prime})=x^{\prime}$

holds, which proves that there is a unique attractor of length $2^{\ell+r-1}$.
From this is derived Theorem 10. It gives some bounds on convergence time.

######  Theorem 10 ([MNR+15]).

Let $\mathscr{D}_{\ell,r}^{-,-}$ be a canonical negative Boolean automata
double-cycle, where $\diamond=\land$. $\mathscr{D}_{\ell,r}^{-,-}$ admits a
unique attractor of length $2^{\ell+r-1}$. In this stable oscillation, any
configuration can be reached from any other in $O(\ell^{2}+r^{2})$ updates.
However, configurations $(\textsf{0}^{\ell},\textsf{0}^{r})$ and
$(\textsf{{1}}^{\ell},\textsf{{1}}^{r})$ can be reached from any other one in
$O(\ell+r)$ updates, and the configurations
$((\textsf{0}\textsf{{1}})^{\frac{\ell}{2}},(\textsf{0}\textsf{{1}})^{\frac{r}{2}})$
and
$((\textsf{{1}}\textsf{0})^{\frac{\ell}{2}},(\textsf{{1}}\textsf{0})^{\frac{r}{2}})$
can reach all the others in $O(\ell+r)$ updates.

Like even negative Boolean automata double-cycles, odd negative Boolean
automata double-cycles also admit a single attractor (a stable oscillation).
However, all configurations are not necessarily recurring. Indeed, they admit
a set $I$ of non-reachable configurations, from which updates are
irreversible. The associated result is formalised in Theorem 11 below.

######  Theorem 11 ([MNR+15]).

Let $\rho:\mathbb{N}\to\\{0,1\\}$, with $\rho(k)=\begin{cases}0&\text{ if
}k=0\text{ or }k\equiv 1\mod 2\\\ 1&\text{otherwise}\end{cases}$. Every
Boolean automata double-cycle $\mathscr{D}_{\ell,r}^{-,-}$ admits a unique
attractor $\mathbb{B}^{\ell+r-1}\setminus I$, where $|I|=\alpha(\ell-1)\times
2^{r-1}+\alpha(r-1)\times 2^{\ell-1}$.

This result, whose proof rests on the characterisation of $I$, generalises
Theorem 10.

##  7 Conclusion

In this chapter, we have summarised the major results obtained in recent years
on the role of feedbacks in interaction networks. The literature has already
established that feedback patterns are "engines of complexity" in the
dynamical behaviours of larger networks that contain them. Because of their
proven essential character, we have therefore deliberately focused on the
dynamics of cycles and double-cycles, by focusing especially on the influence
of updating modes. Without going back on the results themselves, this chapter
highlights the fundamental differences induced by the ``scheduling'' of events
on the behaviours of the complexity engines of interaction networks: while
parallelism tends to render all the asymptotic mathematical diversity of
networks, pure asynchronism tends to reduce degrees of freedom of networks,
which partly explains why the former is often preferred in theoretical work
while the second is often adopted in works that are oriented towards
applications in molecular biology. At present, no real knowledge in molecular
biology establishes precisely how regulations are implemented over time, even
if works state that the chromatin dynamics plays an important role. That is in
particular why the type of studies developed in this chapter, focusing on
updating modes, remains essential to go further in understanding formal and
applied interaction networks. As a consequence, further studies need to be
done on the scheduling of updates over time. A first avenue is to focus for
instance on more likely updating modes, in agreement with the discussion of
what is claimed in [DS20].

Another natural opening highlighted by these works, deeply rooted in
fundamental computer science, consists in developing knowledge on the
dynamical properties of interaction networks, including relationships between
their architecture and structure. But other equally relevant lines of
investigation also call for exploration. One of them was opened up by the
study of asynchronous double-cycles and deals with the time complexity of
networks. A question that remains currently open is the following: does the
time complexity of the networks go hand in hand with their behavioural
diversity? If yes, can we find a measure of it? Finally, the work carried out
on cycles and double-cycles in parallel, developed in [Nou12b, Sen12]
discusses perspectives around computability, modularity/compositionality, and
intrinsic universality of networks. These are certainly, like the ever-growing
understanding of the influences of updating modes, among the most promising
tracks for future works in the field.

##### Acknowledgement

This work was funded mainly by our salaries as French or German State agents
or pensioner (affiliated to Université Grenoble-Alpes (JD), Université d'Évry
(TM and DR), Freie Universität Berlin (MN), and Université d'Aix-Marseille
(SS)), and secondarily by the ANR-18-CE40-0002 FANs project (SS).

## References

  * [AGZ+06] J. Aracena, M. González, A. Zuñiga, M. A. Mendez, and V. Cambiazo.  Regulatory network for cell shape changes during drosophila ventral furrow formation.  Journal of Theoretical Biology, 239:49–62, 2006.
  * [Alb09] R. Albert.  Discrete dynamic modeling of cellular signaling networks.  Methods in Enzymology, 467:281–306, 2009.
  * [Ald03] M. Aldana.  Boolean dynamics of networks with scale-free topology.  Physica D, 185:45–66, 2003.
  * [Apo76] T. M. Apostol.  Introduction to analytic number theory.  Springer-Verlag, 1976.
  * [BCG82] E. R. Berlekamp, J. H. Conway, and R. K. Guy.  Winning ways for your mathematical plays.  Academic Press, 1982.
  * [BP07] J. Berstel and D. Perrin.  The origins of combinatorics on words.  European Journal of Combinatorics, 28:996–1022, 2007.
  * [CD85] M. Cosnard and J. Demongeot.  On the definitions of attractors.  In Iteration theory and its functional equations, volume 1163 of Lecture Notes in Mathematics, pages 23–31. Springer, 1985.
  * [CDLB83] M. Cosnard, J. Demongeot, and A. Le Breton, editors.  Rhythms in biology and other fields of application, volume 49 of Lecture Notes in Biomathematics.  Springer, 1983.
  * [Chu32] A. Church.  A set of postulates for the foundation of logic.  Annals of Mathematics, 33:346–366, 1932.
  * [Coo04] M. Cook.  Universality in elementary cellular automata.  Complex Systems, 15:1–40, 2004.
  * [Cul71] P. Cull.  Linear analysis of switching nets.  Biological Cybernetics, 8:31–39, 1971.
  * [Del49] M. Delbrück.  Génétique du bactériophage.  In Unités biologiques douées de continuité génétique, volume 8 of Colloques internationaux du CNRS, pages 91–103, 1949.
  * [Dem75] J. Demongeot.  Au sujet de quelques modèles stochastiques appliqués à la biologie.  PhD thesis, Université scientifique et médicale de Grenoble, 1975\.
  * [DGM+10] J. Demongeot, E. Goles, M. Morvan, M. Noual, and S. Sené.  Attraction basins as gauges of the robustness against boundary conditions in biological complex systems.  PLoS One, 5:e11793, 2010.
  * [DGT85] J. Demongeot, E. Goles, and M. Tchuente, editors.  Dynamical systems and cellular automata.  Academic Press, 1985.
  * [DNS12] J. Demongeot, M. Noual, and S. Sené.  Combinatorics of Boolean automata circuits dynamics.  Discrete Applied Mathematics, 160:398–415, 2012.
  * [DS20] J. Demongeot and S. Sené.  About block-parallel Boolean networks: a position paper.  Natural Computing, 19:5–13, 2020.
  * [Els59] B. Elspas.  The theory of autonomous linear sequential networks.  IRE Transactions on Circuit Theory, 6:45–60, 1959.
  * [GBK+07] S. Gupta, S. S. Bisht, R. Kukreti, S. Jain, and S. K. Brahmachari.  Boolean network analysis of a neurotransmitter signaling pathway.  Journal of Theoretical Biology, 244:463–469, 2007.
  * [GEHL02] C. C. Guet, M. B. Elowitz, W. Hsing, and S. Leibler.  Combinatorial synthesis of genetic networks.  Science, 296:1466–1470, 2002.
  * [Ger04] C. Gershenson.  Updating schemes in random Boolean networks: do they really matter?  In Proceedings of Artificial Life, pages 238–243. MIT Press, 2004\.
  * [GFSP85] E. Goles, F. Fogelman-Soulié, and D. Pellegrin.  Decreasing energy functions as a tool for studying threshold networks.  Discrete Applied Mathematics, 12:261–277, 1985.
  * [GKP89] R. L. Graham, D. E. Knuth, and O. Patashnik.  Concrete mathematics: a foundation for computer science.  Addison-Wesley, 1989.
  * [GM90] E. Goles and S. Martínez.  Neural and automata networks: dynamical behavior and applications, volume 58 of Mathematics and Its Applications.  Kluwer Academic Publishers, 1990.
  * [GN10] E. Goles and M. Noual.  Block-sequential update schedules and Boolean automata circuits.  In Proceedings of AUTOMATA, pages 41–50. Discrete Mathematics and Theoretical Computer Science, 2010.
  * [Göd86] K. F. Gödel.  Kurt Gödel collected works, volume I – Publications 1929-1936, chapter On undecidable propositions of formal mathematical systems, pages 346–372.  Oxford University Press, 1986.
  * [Gol67] S. W. Golomb.  Shift register sequences.  Holden-Day Inc., 1967.
  * [Gol82] E. Goles.  Fixed point behavior of threshold functions on a finite set.  SIAM Journal on Algebraic and Discrete Methods, 3:529–531, 1982\.
  * [HH70] B. Hesper and P. Hogeweg.  Bioinformatica: een werkconcept.  Kameleon, 1:18–29, 1970.
  * [HH78] P. Hogeweg and B. Hesper.  Interactive instruction on population interactions.  Computers in Biology and Medicine, 8:319–327, 1978.
  * [Huf59] D. A. Huffman.  Canonical forms for information-lossless finite-state logical machines.  IRE Transactions on Information Theory, 5:41–59, 1959.
  * [JM61] F. Jacob and J. Monod.  Genetic regulatory mechanisms in the synthesis of proteins.  Journal of Molecular Biology, 3:318–356, 1961.
  * [Kau69a] S. A. Kauffman.  Homeostasis and differentiation in random genetic control networks.  Nature, 224:177–178, 1969.
  * [Kau69b] S. A. Kauffman.  Metabolic stability and epigenesis in randomly constructed genetic nets.  Journal of Theoretical Biology, 22:437–467, 1969.
  * [Kau71] S. A. Kauffman.  Current topics in developmental biology, volume 6, chapter Gene regulation networks: A theory for their global structures and behaviors, pages 145–181.  Elsevier, 1971.
  * [KL80] H. T. Kung and C. E. Leiserson.  Introduction to VLSI systems, chapter Algorithms for VLSI processor arrays, pages 271–292.  Addison-Wesley, 1980.
  * [Kle56] S. C. Kleene.  Automata studies, volume 34 of Annals of Mathematics Studies, chapter Representation of events in nerve nets and finite automata, pages 3–41.  Princeton Universtity Press, 1956.
  * [KPST03] S. A. Kauffman, C. Peterson, B. Samuelsson, and C. Troein.  Random Boolean network models and the yeast transcriptional network.  Proceedings of the National Academy of Sciences of the USA, 100:14796–14799, 2003.
  * [KT85] M. Kaufman and R. Thomas.  Towards a logical analysis of the immune response.  Journal of Theoretical Biology, 114:527–561, 1985.
  * [Kur97] P. Kurka.  Languages, equicontinuity and attractors in cellular automata.  Ergodic Theory and Dynamical Systems, 17:417–433, 1997.
  * [MAB98] L. Mendoza and E. R. Alvarez-Buylla.  Dynamics of the genetic regulatory network for _Arabidopsis thaliana_ flower morphogenesis.  Journal of Theoretical Biology, 193:307–319, 1998.
  * [MCJ63] J. Monod, J.-P. Changeux, and F. Jacob.  Allosteric proteins and cellular control systems.  Journal of Molecular Biology, 6:306–329, 1963.
  * [Men06] L. Mendoza.  A network model for the control of the differentiation process in Th cells.  Biosystems, 84:101–114, 2006.
  * [MNR+15] T. Melliti, M. Noual, D. Regnault, S. Sené, and J. Sobieraj.  Asynchronous dynamics of Boolean automata double-cycles.  In Proceedings of UCNC, volume 9252 of Lecture Notes in Computer Science, pages 250–262. Springer, 2015.
  * [MP43] W. S. McCulloch and W. Pitts.  A logical calculus of the ideas immanent in nervous activity.  Journal of Mathematical Biophysics, 5:115–133, 1943.
  * [Nou12a] M. Noual.  Dynamics of circuits and intersection circuits.  In Proceedings of LATA, volume 7183 of Lecture Notes in Computer Science, pages 433–444. Springer, 2012.
  * [Nou12b] M. Noual.  Updating automata networks.  PhD thesis, École normale supérieure de Lyon, 2012.  http://tel.archives-ouvertes.fr/tel-00726560.
  * [PW01] Y. Puri and T. Ward.  Arithmetic and growth of periodic orbits.  Journal of Integer Sequences, 4:01.2.1, 2001.
  * [RC07] A. Richard and J.-P. Comet.  Necessary conditions for multistationarity in discrete dynamical systems.  Discrete Applied Mathematics, 155:2403–2413, 2007.
  * [RCB04] A. Richard, J.-P. Comet, and G. Bernot.  R. Thomas' modeling of biological regulatory networks: introduction of singular states in the qualitative dynamics.  Fundamenta Informaticae, 65:373–392, 2004.
  * [RGS18] G. A. Ruz, E. Goles, and S. Sené.  Reconstruction of Boolean regulatory models of flower development exploiting an evolution strategy.  In Proceedings of CEC, pages 1–8. IEEE Press, 2018.
  * [Rib96] P. Ribenboim.  The new book of prime number records.  Springer-Verlag, 1996.
  * [Ric10] A. Richard.  Negative circuits and sustained oscillations in asynchronous automata networks.  Advances in Applied Mathematics, 44:378–392, 2010.
  * [RMCT03] É. Remy, B. Mossé, C. Chaouiya, and D. Thieffry.  A description of dynamical graphs associated to elementary regulatory circuits.  Bioinformatics, 19:ii172–ii178, 2003.
  * [Rob69] F. Robert.  Blocs-H-matrices et convergence des méthodes itératives classiques par blocs.  Linear Algebra and its Applications, 2:223–265, 1969.
  * [Rob76] F. Robert.  Contraction en norme vectorielle: convergence d'itérations chaotiques pour des équations non linéaires de point fixe à plusieurs variables.  Linear Algebra and its Applications, 13:19–35, 1976.
  * [Rob80] F. Robert.  Itérations sur des ensembles finis et automates cellulaires contractants.  Linear Algebra and its Applications, 29:393–412, 1980.
  * [Rob86] F. Robert.  Discrete iterations: a metric study, volume 6 of Springer Series in Computational Mathematics.  Springer, 1986.
  * [Rob95] F. Robert.  Les systèmes dynamiques discrets, volume 19 of Mathématiques & Applications.  Springer, 1995.
  * [RRT08] É. Remy, P. Ruet, and D. Thieffry.  Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework.  Advances in Applied Mathematics, 41:335–350, 2008.
  * [Rus03] F. Ruskey.  Combinatorial generation.  Book preliminary working draft, 2003.
  * [Sen12] S. Sené.  Sur la bio-informatique des réseaux d'automates.  Habilitation thesis, Université d'Évry – Val d'Essonne, 2012\.  http://tel.archives-ouvertes.fr/tel-00759287.
  * [Smi71] A. R. Smith.  Simple computation-universal cellular spaces.  Journal of the ACM, 18:339–353, 1971.
  * [SRSL+07] J. Saez-Rodriguez, L. Simeoni, J. A. Lindquist, R. Hemenway, U. Bommhardt, Arndt B., U.-U. Haus, R. Weismantel, E. D. Gilles, S. Klamt, and B. Schraven.  A logical model provides insights into T cell receptor signaling.  PLoS Computational Biology, 3:e163, 2007.
  * [Tho73] R. Thomas.  Boolean formalization of genetic control circuits.  Journal of Theoretical Biology, 42:563–585, 1973.
  * [Tho81] R. Thomas.  On the relation between the logical structure of systems and their ability to generate multiple steady states or sustained oscillations.  In Numerical methods in the study of critical phenomena, volume 9 of Springer Series in Synergetics, pages 180–193. Springer, 1981\.
  * [Tho91] R. Thomas.  Regulatory networks seen as asynchronous automata: a logical description.  Journal of Theoretical Biology, 153:1–23, 1991.
  * [TT95] D. Thieffry and R. Thomas.  Dynamical behaviour of biological regulatory networks – II. Immunity control in bacteriophage lambda.  Bulletin of Mathematical Biology, 57:277–297, 1995.
  * [TTK95] R. Thomas, D. Thieffry, and M. Kaufman.  Dynamical behaviour of biological regulatory networks – I. Biological role of feedback loops and practical use of the concept of the loop-characteristic state.  Bulletin of Mathematical Biology, 57:247–276, 1995.
  * [Tur36] A. M. Turing.  On computable numbers, with an application to the entscheidungsproblem.  Proceedings of the London Mathematical Society, 2:230–265, 1936\.
  * [van60] H. van der Laan.  Le nombre plastique, quinze leçons sur l'ordonnance architectonique.  E.J. Brill, 1960.
  * [von66] J. von Neumann.  Theory of self-reproducing automata.  University of Illinois Press, 1966.
  * [Wol84] S. Wolfram.  Universality and complexity in cellular automata.  Physica D, 10:1–35, 1984.