# On the Periods of Parallel Dynamical Systems

Authors: Juan A. Aledo; Luis G. Diaz; Silvia Martinez; Jose C. Valverde
Journal: Complexity
 (2017)

---

## Abstract

In this work, we provide conditions to obtain fixed point theorems for parallel dynamical systems over graphs with (Boolean) maxterms and minterms as global evolution operators. In order to do that, we previously prove that periodic orbits of different periods cannot coexist, which implies that Sharkovsky’s order is not valid for this kind of dynamical systems.


---

## Body

## 1. Introduction

It is beyond dispute that mathematical modeling of real phenomena is one of the main tasks of applied mathematics nowadays. Nevertheless, once a model fits a phenomenon, it is necessary to analyze such a model theoretically in order to apply the results found to any particular case under study.In the last two decades,graph dynamical systems (GDS) have been revealed as an important tool for the mathematical modeling of computer processes. For the formulation of such models, these systems are decomposed into the lower unities of aggregation, calledentities, where each entity i has a (numerical) value x
i which represents its state. When the possible states of each entity are activated or deactivated, the state value of an entity i is formalized by considering x
i
∈
{
0,1
}. Indeed, the state values can belong to a more general Boolean algebra [1]. The relations among entities are represented by a graph called thedependency graph of the system, while the evolution or update of the system is implemented bylocal (Boolean) functions which together constitute a global (evolution) operator. That is, for the dynamic evolution of the state of any entity, the corresponding local function acts on such state and those ones corresponding to entities related to it.When the states of the entities are updated in a synchronous manner, the system is called aparallel dynamical system (PDS) [2, 3], while if they are updated in an asynchronous way, the system is namedsequential dynamical system (SDS) [4].Other tools for mathematical modeling as cellular automata (CA) [5–11] or Boolean networks (BN) [12–14] are particular cases of PDS [15]. It shows the enormous versatility of this new paradigm, which has applications to different branches of sciences as biology [12, 16, 17], ecology [18–20], mathematics [21, 22], cryptography [23, 24], physics [25], and chemistry [26]. (The abbreviations GDS, PDS, SDS, CA, and BN will be written for the singular and plural forms of the corresponding terms, since it seems better from an aesthetic point of view.)The main aim regarding the study of a dynamical system is to give a complete characterization of its orbit structure [27]. That is, to derive as much information as possible about the phase diagram, based on the initial states and the evolution operator of the system. Specifically, as pointed out in [28], it means to determine the length and number of coexisting limit cycles and which different initial states arrive in the same limit cycle.Concerning these questions, in [3] PDS and SDS are studied, considering the simplest Boolean functions OR (resp., AND) and NOR (resp., NAND) as global evolution operators. These results are extended in [2] for PDS with any general Boolean maxterm (resp., minterm) as global functions; in particular, it is proved that for such PDS uniquely periodic or eventually periodic orbits of period lower than or equal to 2 are possible.The results in [2] left open some questions among those set out by Derrida and Pomeau [28] regarding the phase diagram of such systems. One of them consists in studying the coexistence of periodic orbits of different periods for PDS with general maxterm (resp., minterm) functions as evolution operators in the same sense of Sharkovsky’s Theorem [29, 30]. In other words, it consists in guessing whether the existence of certain periods implies the appearance of other ones in a similar way to Sharkovsky’s order.Concerning this question, in this work, we show that Sharkovsky’s Theorem and the order established with it do not apply in the context of PDS. On the contrary, we demonstrate that the coexistence of periodic orbits with different periods is not possible.The main objective of this paper is to establish results for PDS with general maxterm (resp., minterm) functions as evolution operators in the sense of the fixed point theorem by Banach. In fact, as we show in Example8, there exists PDS with several fixed points and so it naturally arises the problem of determining conditions which guarantee the uniqueness of a fixed point.The results, which are initially given for state values of the entities in the basic Boolean algebra{
0,1
}, are later generalized for state values belonging to any general Boolean algebra with 2
p elements, p
∈
N, p
≥
1.The specific systems treated in this work appear when modeling real physical phenomena like the dynamics of genes. In particular, when studying gene regulatory networks, it is observed that the binding sites of genes regulated by more than one gene exhibit synergistic effects. This could be modeled by conjunctive Boolean networks, but they do not allow modeling inhibitory regulation, what needs from minterms evolution operators to formalize and analyze the corresponding dynamics (see [31]).The paper is organized as follows. Section2 gives some preliminaries concerning PDS on maxterm and minterm Boolean functions. In Section 3, we demonstrate that the coexistence of periodic orbits with different periods is not possible, so showing that Sharkovsky’s Theorem does not apply in this context. In Section 4, we establish a fixed point theorem for a PDS. In Section 5, we extend our results to PDS with state values belonging to any general Boolean algebra with 2
p elements. Finally, Section 6 provides some conclusions and future research directions.


## 2. Preliminaries

In this section we revise some basic notions regardingparallel dynamical system (PDS) (see [15] and the references therein for the details).As is well known, a PDS is totally determined by itsdependency graph and itsevolution orupdating function, which we briefly describe below.The dependency graph is given by a (undirected) graphG
=
(
V
,
E
), where V
=
{
1,2
,
…
,
n
} is the vertex set and E is the edge set. We will represent by x
i
∈
{
0,1
} thestate of the vertex i
∈
V, meaning that the vertex i isactivated (x
i
=
1) ordeactivated (x
i
=
0).We will assume thatG is connected; otherwise the reasonings and results which we will provide can be easily adapted by working on its connected components.For every vertexi
∈
V, we will consider the set A
G
(
i
)
⊆
V of vertices that are adjacent to i; namely,(1)
A
G
i
=
j
∈
V
∣
i
,
j
∈
E
. Then, given W
⊆
V, we define(2)
A
G
W
=
⋃
i
∈
W
A
G
i
.The evolution or update of the system is implemented by local functions{
f
i
}
i
∈
V which, for every i
∈
V, act only over {
i
}
∪
A
G
(
i
).Definition 1.
LetG
=
(
V
,
E
) be a graph on V
=
{
1,2
,
…
,
n
}. Then a map(3)
F
:
0,1
n
⟶
0,1
n
,
F
x
1
,
x
2
,
…
,
x
i
,
…
,
x
n
=
y
1
,
y
2
,
…
,
y
i
,
…
,
y
n
,where y
i is the updated state of the entity i by applying a local function f
i over the states of the entities in {
i
}
∪
A
G
(
i
), constitutes a discrete dynamical system calledparallel dynamical system (PDS) over {
0,1
}
n.Everyf
i is often the restriction of the global function F acting only over the state of the entities in {
i
}
∪
A
G
(
i
), as we are going to suppose in this document. Nevertheless, each f
i could be seen as another function F
i:(4)
F
i
=
0,1
n
⟶
0,1
,
F
i
x
1
,
x
2
,
…
,
x
i
,
…
,
x
n
=
y
i
, such that F
=
(
F
1
,
F
2
,
…
,
F
n
).In particular, the (global) evolution operator of a PDS can be given by means of aBoolean function of n variables:(5)
F
:
0,1
n
⟶
0,1
,where F
(
x
1
,
x
2
,
…
,
x
n
) is obtained from x
1
,
x
2
,
…
,
x
n
∈
{
0,1
} using the logical AND (∧), the logical OR (∨), the logical NOT (′), and the elements 0,1. Particular cases of Boolean functions aremaxterms andminterms. Recall that a maxterm (resp., minterm) of n variables x
1
,
x
2
,
…
,
x
n is a Boolean function F such as(6)
F
x
1
,
x
2
,
…
,
x
n
=
z
1
∨
z
2
∨
⋯
∨
z
n
r
e
s
p
.
F
x
1
,
x
2
,
…
,
x
n
=
z
1
∧
z
2
∧
⋯
∧
z
n
, where z
i
=
x
i or z
i
=
x
i
′.In this work, we deal with this special kind of PDS.Definition 2.
LetG
=
(
V
,
E
) be a (undirected) graph with V
=
{
1,2
,
…
,
n
}. Then the following (evolution) operator(7)
F
:
0,1
n
⟶
0,1
n
,
F
x
1
,
x
2
,
…
,
x
n
=
y
1
,
y
2
,
…
,
y
n
,where y
i is the updated state of the entity i by applying locally the Boolean function F over the states of the vertices in {
i
}
∪
A
G
(
i
), constitutes a PDS over G with the Boolean function F as evolution operator, which will be denoted by [
G
,
F
] or F-PDS when specifying that the dependency graph is not necessary.In particular, we will represent by MAX-PDS (resp., MIN-PDS) a PDS whose evolution operator is the maxterm MAX (resp., the minterm MIN).


## 3. Coexistence of Periodic Orbits in PDS over Graphs

In [2] it was shown that the periodic orbits of a MAX-PDS (resp., MIN-PDS) are fixed points or 2-periodic orbits. Moreover, when the maxterm MAX (resp., minterm MIN) has all the variables in its direct form, then only (eventually) fixed points can appear, while if it has all the variables in its complemented form, then only (eventually) 2-periodic orbits are possible.However, some important questions remained open. One of them consists in studying the coexistence of periodic orbits with different periods in the same sense of Sharkovsky’s Theorem [29, 30] for PDS with general maxterm (resp., minterm) functions as evolution operators. In other words, it consists in guessing whether the existence of certain periods implies the appearance of other ones in a similar way to Sharkovsky’s order. Concerning this question, in this section, we prove that Sharkovsky’s Theorem and the order established with it do not apply in the context of PDS. In fact, we demonstrate that periodic orbits with different periods cannot coexist.In order to do that, next, we describe which structure a PDS must have in order to admit (eventually) fixed points. We will outline the reasonings for the case of a MAX-PDS, although all of them can be dually rewritten for a MIN-PDS.Theorem 3.
Let MAX-PDS be the PDS over a dependency graphG
=
(
V
,
E
) associated with the maxterm MAX. All the periodic orbits of this system are fixed points if, and only if, every entity whose state variable in MAX is in complemented form is adjacent to an entity whose state variable in MAX is in directed form.Proof.
Let us consider the setW
⊆
V (resp., W
′
⊆
V) of vertices in V such that the corresponding variables in MAX appear in direct (resp., complemented) form.
First, assume that all the periodic orbits of this system are fixed points.
In the caseW
′
=
∅, the system has two fixed points: the one with all the variables activated and the one with all of them deactivated (see [2, 3]).
Thus, assume thatW
′
≠
∅ and take x
^
=
(
x
^
1
,
x
^
2
,
…
,
x
^
n
) a fixed point, where x
^
i represents the (fixed) value of the vertex i
∈
V. Note that, for all i
∈
W
′, it must be x
^
i
=
1. Otherwise (i.e., if x
^
i
=
0), it would change to 1 after the following iteration.
Suppose that there existsi
∈
W
′ such that W
∩
A
G
(
i
)
=
∅. In such a case A
G
(
i
)
⊆
W
′ and so for every j
∈
A
G
(
i
) it is x
^
j
=
x
^
i
=
1. But this is not possible, since in the following iteration the value of i would change to 0, which is a contradiction.
To prove the converse implication, let us suppose that for alli
∈
W
′ it is W
∩
A
G
(
i
)
≠
∅. We will write x
i
k to indicate the state value of the entity i after k iterations of the evolution operator MAX. Thus, let us consider an arbitrary initial value for the variables (
x
1
0
,
x
2
0
,
…
,
x
n
0
). Since the dependency graph is finite (and so is the state space), note that after a certain number of iterations, let us say m
∈
N, the states of all the vertices i
∈
W become fixed. Let us take i
∈
W
′ and let us prove that it is x
i
m
+
1
=
1. In fact, let us suppose that x
i
m
+
1
=
0 and take j
∈
W
∩
A
G
(
i
). Then it would be x
j
m
+
2
=
1
=
x
j
m (since we are assuming that the state value of j is fixed from the iteration m). But then, since x
j
m
=
1, it must be x
i
m
+
1
=
1, which is a contradiction. Thus, it is x
i
m
+
1
=
1 for all i
∈
W
′ and these state values do not change as can be easily inferred from the reasoning above.
Therefore, all the variables of the system become fixed afterm
+
1 iterations and the proof finishes.Dually, we have the following.Theorem 4.
Let MIN-PDS be the PDS over a dependency graphG
=
(
V
,
E
) associated with the minterm MIN. All the periodic orbits of this system are fixed points if, and only if, every entity whose state variable in MIN is in complemented form is adjacent to an entity whose state variable in MIN is in directed form.Analogously, dual results can be obtained for all the following results. For the sake of conciseness, we will not state them.Since all the periodic orbits of the system are fixed points or 2-periodic orbits (see [2]), as a consequence of Theorem 3 we have the following.Theorem 5.
Let MAX-PDS be the PDS over a dependency graphG
=
(
V
,
E
) associated with the maxterm MAX. All the periodic orbits of this system are 2-periodic orbits if, and only if, there exists an entity whose state variable in MAX is in complemented form which is not adjacent to any entity whose state variable in MAX is in directed form.Proof.
First, assume that all the periodic orbits of this system are 2-periodic orbits. If the theses were not true, that is, if for alli
∈
W
′, it is W
∩
A
G
(
i
)
≠
∅, then from Theorem 3 we have that all the periodic orbits of this system are fixed points, which is a contradiction.
Conversely, let us suppose that there existsi
∈
W
′ such that W
∩
A
G
(
i
)
=
∅. If the system has a fixed point, reasoning as in the proof of Theorem 3, we get that every entity whose state variable in MAX is in complemented form is adjacent to an entity whose state variable in MAX is in directed form, which is a contradiction. Hence, all the periodic orbits of the system must be 2-periodic orbits.Remark 6.
Note that the cases when the evolution operator of the system is AND, OR, NAND, and NOR studied in [3] can be immediately obtained as particular cases of Theorems 3 and 5.As a direct consequence of Theorems3 and 5, we get the main result of this section.Theorem 7.
Let MAX-PDS be the PDS over a dependency graphG
=
(
V
,
E
) associated with the maxterm MAX. Then (eventually) fixed points and (eventually) 2-periodic orbits cannot coexist.


## 4. A Fixed Point Theorem for PDS over Graphs

As commented in the introduction, our main objective is to obtain a fixed point theorem for PDS. Observe that, although fixed points and 2-periodic orbits cannot coexist, there are PDS whose state spaces contain more than one fixed point as shown in the following example.Example 8 (PDS with more than a fixed point).
Let us consider the graphG
=
(
V
,
E
) with V
=
{
1,2
,
3
} and E
=
{
{
1,2
}
,
{
2,3
}
}, and let us take the evolution operator(8)
F
x
1
,
x
2
,
x
3
=
x
1
∨
x
2
′
∨
x
3
. The fixed points of this PDS are (
1,1
,
0
), (
0,1
,
1
), and (
1,1
,
1
).Thus, it would be desirable to find conditions to assure that the system has a unique fixed point. In order to do that, assume that the MAX-PDS has at least a fixed point; that is, for every vertexi
∈
W
′ it is W
∩
A
G
(
i
)
≠
∅ (see Theorem 3).LetG
1
,
G
2
,
…
,
G
p be the connected components which result from G when we remove all the vertices in W
′ and the edges adjacent to those vertices. We will say that a vertex i in W
′ and a connected component G
j are adjacent if i is adjacent to any vertex of G
j. Let us consider the subsets W
1
′ and W
2
′ of W
′ given by(9)
W
1
′
=
i
∈
W
′
:
t
h
e
r
e
e
x
i
s
t
s
a
u
n
i
q
u
e
j
,
1
≤
j
≤
p
,
s
u
c
h
t
h
a
t
i
i
s
a
d
j
a
c
e
n
t
t
o
G
j
W
2
′
=
W
′
∖
W
1
′
.Letx
^
=
(
x
^
1
,
x
^
2
,
…
,
x
^
n
) be a fixed point of the system. As we have showed in the proof of Theorem 3, for all i
∈
W
′, it is x
^
i
=
1.Furthermore, ifj, 1
≤
j
≤
p, is such that A
G
(
G
j
)
∩
W
1
′
≠
∅, then for all i
∈
G
j it is x
^
i
=
1. In order to see that, note that in the fixed point x
^ all the vertices in G
j must be either activated or deactivated. Let us take k
∈
A
G
(
G
j
)
∩
W
1
′. Then, if it is x
^
i
=
0 for all i
∈
G
j and since it is x
^
i
=
1 for all i
∈
A
G
(
k
)
∩
W
′, then the state of k will change to 0 after the next iteration, which is a contradiction.Therefore, if for everyj, 1
≤
j
≤
p, it is A
G
(
G
j
)
∩
W
1
′
≠
∅, then the system has a unique fixed point: the one with all the variables activated.On the other hand, if for aj, 1
≤
j
≤
p, it is A
G
(
G
j
)
∩
W
1
′
=
∅, then in a fixed point two situations are possible: either all the vertices in G
j are activated or all of them are deactivated. Regarding this last comment, we must point out that given i
∈
W
2
′, if G
i
1
,
G
i
2
,
…
,
G
i
l
(
i
), 2
≤
l
(
i
)
≤
p are the connected components adjacent to i, then not all these components can be deactivated simultaneously in the fixed point; otherwise the value of x
i would change from 1 to 0 in the following iteration.In view of the explanations above, we have proved the following result.Theorem 9.
Let MAX-PDS be the PDS over a dependency graphG
=
(
V
,
E
) associated with the maxterm MAX and assume that for all i
∈
W
′ it is W
∩
A
G
(
i
)
≠
∅. This PDS has a unique fixed point if, and only if, for every j, 1
≤
j
≤
p, it is A
G
(
G
j
)
∩
W
1
′
≠
∅. In this situation, the only fixed point is the one with all the vertices activated.


## 5. Fixed Point Theorem for PDS over Graphs with General Boolean States

In the recent work [1], a generalization of PDS over graphs is introduced by considering that the states of the entities can take values in an arbitrary Boolean algebra (
B
,
⋎
,
⋏
,
′
,
O
,
I
) with 2
p elements, p
∈
N, p
≥
1. We represent such a PDS as [
B
,
G
,
M
A
X
] (resp., [
B
,
G
,
M
I
N
]) to indicate the dependency graph G and the maxterm MAX (resp., minterm MIN) taken as evolution operator. Note that the previous study corresponds to the particular case where B
=
{
0,1
}; that is, p
=
1.In such a work, it was proved that the periodic orbits of these more general PDS are also fixed points or 2-periodic orbits. The key idea to prove this result consists in using the Stone Representation Theorem for Boolean Algebras in a suitable way todecompose this general dynamical system into p PDS where the entities take values in {
0,1
} (see [1, Section 3] for the details).Then, from our study above, a straightforward reasoning allows checking that all the results in Sections3 and 4 are also true for PDS where the states of the entities take values in an arbitrary Boolean algebra. That is, (eventually) fixed points and (eventually) 2-periodic orbits cannot coexist.Theorem 10.
Let[
B
,
G
,
M
A
X
] be the PDS over a dependency graph G
=
(
V
,
E
) associated with the maxterm MAX. Then (eventually) fixed points and (eventually) 2-periodic orbits cannot coexist.In particular, we have a fixed point theorem in this more general context as stated belowTheorem 11.
Let[
B
,
G
,
M
A
X
] be the PDS over a dependency graph G
=
(
V
,
E
) associated with the maxterm M
A
X and assume that for all i
∈
W
′ it is W
∩
A
G
(
i
)
≠
∅. This PDS has a unique fixed point if, and only if, for every j, 1
≤
j
≤
p, it is A
G
(
G
j
)
∩
W
1
′
≠
∅. In this situation, the only fixed point is the one with the state of all the vertices equal to I
∈
B.Proof.
Since this general dynamical system can be decomposed intop PDS where the entities take values in {
0,1
} and all of these p PDS are defined on the same dependency graph G, the system [
B
,
G
,
M
A
X
] has a unique fixed point, resembling the one of [
{
0,1
}
,
G
,
M
A
X
], just identifying the value 0
∈
{
0,1
} with O
∈
B and 1
∈
{
0,1
} with I
∈
B.


## 6. Conclusions and Future Research Directions

This paper provides a significant advance in the description of the phase diagram of PDS over graphs on (global) Boolean operators, by analyzing the veracity of two classical theorems in dynamical systems theory in this framework.In particular, we demonstrate that the coexistence of periodic orbits with different period is impossible in such systems. This means that Sharkovsky’s Theorem for discrete dynamical systems associated with continuous functions is not true in the context of PDS. We also obtain a fixed point theorem for this kind of dynamical systems, providing conditions which assure the uniqueness of a fixed point for the PDS. In other words, we characterize the PDS where any initial state evolves to an equilibrium which, for real models, is a meaningful piece of information.Finally, by using the techniques provided in this work, the results here obtained invite studying the same problems in other types of GDS, as those on directed graphs [32] and/or those where the evolution operator is given by means of local independent Boolean functions [33].Other tools for mathematical modeling as cellular automata (CA) or Boolean networks (BN) are particular cases of PDS when considering the same evolution operator. That is, CA and BN on maxterm (resp., minterm) Boolean functions over undirected graphs are particular cases of PDS with maxterm (resp., minterm) that we treat in this work. It shows the applicability to different branches of sciences and engineering that this new paradigm of PDS can have.



---

*Source: 7209762-2017-01-12.xml*