# Predecessors Existence Problems and Gardens of Eden in Sequential Dynamical Systems

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

---

## Abstract

In this paper, we deal with one of the main computational questions in network models: the predecessor-existence problems. In particular, we solve algebraically such problems in sequential dynamical systems on maxterm and minterm Boolean functions. We also provide a description of the Garden-of-Eden configurations of any system, giving the best upper bound for the number of Garden-of-Eden points.


---

## Body

## 1. Introduction

Network models are the natural way to formalize the evolution of any phenomenon that includes cells, gens, entities, or any kind of distinct elements which interact among them. Thus, it is not amazing the big amount of papers, published in the last decades, associated with sciences (see, for instance, [1–18]) and engineering (see, for instance, [19–24]), where such models appear to represent different phenomena and study their behavior.Usually, the possible states of the elements of a network model are represented by a (finite) number setK, which we will callstate set. One of the most common cases occurs when such states are on-off, as happens in computer processes, where the number set representing such states values is the basic Boolean algebra {0,1}. However, K could have a more complex structure as, for example, a general Boolean algebra with 2n elements, for n∈N (see [25]).The interaction among the elements of the phenomena is mathematically modeled by a graph calleddependency orwiring graph. In such a graph, the elements are formalized by nodes and an edge between two nodes represents some kind of relation. When the relations are only unidirectional, they are usually namedinfluences and the graph is directed (see, for instance, [26]), with arcs instead of edges. Commonly, the graphs employed in such models arecombinatorial; that is, they have no multiple edges or arcs and they are also loop-free.The evolution of the phenomenon is normally modeled by an operator which consists of local functions that provide the evolution of any vertex, depending on the relation of such a vertex with other vertices. In view of this, these local functions are also calledvertex functions [27]. When the vertex functions correspond to the restriction of the operator to every vertex and their related ones, the model is said to behomogeneous. Other less restricted possibility is that the vertex functions are independent as, for instance, in [28]. When the state set is a Boolean algebra, the vertex functions are given by Boolean functions.The interactions among elements of a phenomenon do typically not occur simultaneously. When it occurs, it is said that the modelupdates synchronously orparallelly (see [25, 26, 28–36]); otherwise it is said that the model updatesasynchronously orsequentially (see [20, 27, 37–41]). In this last case, anupdate order is needed to specify the sequence in which the states of the elements evolve. The update order is usually formalized by permutations or finite words over the vertex set of the corresponding wiring graph.The above four features (i.e., state set, wiring graph, local functions, and update order) determine the most of network models. But, to get a fair model, one should also think if the phenomenon under modelization has some random aspects, as happens, for example, in an infection model, that is, if the system isstochastic or, in contrast, it isdeterministic. Stochastic network models can be obtained by choosing relations among elements, local functions, or update orders randomly at every (iteration) time t.In this work, we deal with deterministic network models which are discrete-time dynamical systems. In particular, we focus on models for which the state set is{0,1}; the wiring graph could be any combinatorial one; the local functions are restriction of a global operator, given by a maxterm or minterm Boolean function; and the update order is a vertex-indexed permutation. These models will be referred to assequential dynamical systems (SDS) on maxterm and minterm Boolean functions.SDS are useful to model phenomena (as evolution of electrical power networks, disease propagation across a social contact network, traffic in large urban areas, transport computations, etc.) where causal dependencies among the elements exist (see [27]). In fact,parallel dynamical systems (PDS) can be seen as a particular case of such models by means of the principle of doubling the graph as shown in [27]. Moreover, SDS generalize the concept of the pioneers network models given by the original cellular automata (CA) [42] or Boolean networks (BN) [14]. (The abbreviations SDS, PDS, CA, BN, and GOE will be written for the singular and plural forms of the corresponding terms, since it seems better from an aesthetic point of view).Once a SDS is set out, to know the evolution of a phenomenon under modelization, we need to describe the phase portrait of such a dynamical system in relation to the state set, the wiring graph, the local functions, and the update order. The phase portrait is always a directed graph, consisting of disconnected cycles that could be reached by trees. The system states in such cycles are calledperiodic, while the rest of them are calledeventually periodic. In particular, the leaves of the trees are said to beGardens of Eden (GOE), while the rest of the system states in the trees are calledtransient states. In view of this, to know the dynamics, we need to derive as much information as possible about the periodic structure of the SDS and their transient and GOE points.The periodic structure of SDS on maxterm and minterm Boolean functions is studied in [37], where it is proved that any period can appear in their phase portrait, although fixed points cannot coexist with other periods. This issue is someway a generalization of the results in PDS on the same Boolean functions [29, 33], where only fixed points and 2-periodic orbits can appear but not coexist. This generalization on the periodic structure, obtained when passing from PDS to SDS, motivates the study of the behavior of the rest of the states for SDS that we perform in this work.Given a SDS, the dynamics of the rest of the states can be obtained computationally by brute-force, using algorithms like those in [34, 40]. But, unfortunately, the results in such computations are only valid for such a SDS. Thus, in this work, we try to extract information (algebraically) about the dynamics of such states by exploring the properties of the SDS in relation to its four fundamental features.Thepredecessor-existence problems, whose solution gives the GOE and transient points, have been traditionally considered as a computational question together with other ones as thereachability problem or thepermutation-existence problem (see [27, 38, 39, 41, 43, 44]). Jointly with the predecessor existence problem (PRE), other related problems are often studied as the unique predecessor problem (UPRE), the coexistence of predecessors problem (APRE), and the number of predecessors problem (#PRE) [43].As for the periodic structure, the results here obtained for SDS in relation to the existence of predecessors and GOE not only suppose an algebraic solution for such problems, but they constitute a generalization to those achieved for PDS in [31].This paper is organized as follows. Section2 presents some basic notations and background on SDS. In Section 3, the PRE problem is solved for SDS on maxterm and minterm Boolean functions. In particular, we provide afundamental predecessor which exists when the state has predecessors. As a consequence, we give conditions that characterize GOE and provide bounds for the number of such states. Mathematical conditions for the UPRE and APRE problems are also given. Besides, we provide upper bounds for the #PRE problem which are the best possible. Finally, Section 4 shows some conclusions and future research directions.


## 2. Preliminaries

In this section, some fundamental concepts about sequential dynamical systems (SDS) are revised. For further reading, more details on this topic can be found in [27] and the references therein.A sequential dynamical system is given by three basic elements associated with the state set of the entities:(i)
A dependency graph modelling the relations among the entities.(ii)
A global function showing the influence of the states of the entities in the evolution.(iii)
A permutation of the vertices of the dependency graph that indicates the order in which the entities are updated.Let us proceed with a contextualization of such elements into this type of system.The dependency graph is an undirected graphG=V,E, where V={1,…,n} is the vertex set and each element i belonging to V is called a vertex or entity of the system, and E is the edge set containing the adjacency relationships among the entities. Each one of these vertices can be activated or deactivated, and it will be represented for the entity i∈V, respectively, as xi=1 or xi=0, being these values the associated state values of the entities.It will be assumed along this document thatG is connected because, otherwise, the results can be generalized simply by working on each connected component.For each entityi∈V, as in [31], let us consider the set AGi⊆V as(1)AGi=j∈V:i,j∈E∪ithat is, the set of all the entities that interfere with i in its update. Similarly, for W⊆V, we denote(2)AGW=⋃i∈WAGiAlso, let us consider the following sets:(3)AG∗i=AGi∖iAG∗W=AGW∖WWe will denote the complementary of a set by using the upper script c. For example, AGcW will be the subset of entities belonging to V which do not belong to AGW.The update (or evolution) of the system is given by local functions{fi}i∈V, for each i∈V. Although these functions may be independent [28], in this document we will assume that they are the restriction of a global function f over AGi. This kind of systems is called homogeneous.In particular, this global evolution operator can be described from a Boolean function ofn variables:(4)F:0,1n→0,1nwhere the evaluation Fx1,…,xn is computed from the values x1,…,xn∈{0,1} using the logical operators AND, OR, and NOT.Some relevant cases of Boolean functions are the maxterms and minterms. Recall that a maxterm (resp., minterm) ofn variables is a Boolean function f such that(5)fx1,…,xn=z1∨⋯∨znresp.fx1,…,xn=z1∧⋯∧zn,being zi=xi or zi=xi′.Since the functionf originates F, sometimes in this document the name of f can be assimilated by F.Finally, the order relationship between the vertices of the dependency graph indicates the order in which the states of the entities are updated. It is given by a permutation onV, π=π1∣π2∣⋯∣πn, where π1 is the first entity whose state updates, π2 the second one, and so on.Summarizing, we have the following.Definition 1.
LetG=V,E be an undirected graph with V=1,…,n, π=π1∣π2∣⋯∣πn a permutation on V and(6)F,π=Fπn∘…∘Fπ1:0,1n→0,1n,a Boolean function such that Fπi:{0,1}n→{0,1}n updates the state of the entity πi∈V considering the state values of the entities belonging to AGi, keeping the other states unaltered. We will denote by G,F,π-SDS the sequential (discrete) dynamical system over G with evolution operator F,π.Along this document, we will use indistinctlyF,π and F to mention the evolution operator since π is implicit in the evaluation of the Boolean function in this context of SDS.The fundamental idea which motivates this document is that the key to understand a dynamical system is knowing its orbits and its phase diagram, i.e., the split of the state space into its orbits.Definition 2.
LetG,F,π-SDS be a sequential dynamical system and x=(x1,…,xn)∈{0,1}n. The orbit in the SDS starting at x is the subset of the state space {0,1}n given by(7)Orbx=y=y1,…,yn∈0,1n:Ftx=y,∀t∈NThe orbits in a SDS are sorted lists of states. WhenFx=y, y is called the successor of x. A configuration y can be successor of more than one state, which are its predecessors. When it happens, the system is called dissipative.If there is nox such that Fx=y, i.e., if y is a configuration without a predecessor, then y is called Garden of Eden (GOE) of the system.Given a generic configurationy, we define the following subsets of V, which will be useful throughout this document.Let us consider the split ofV into the following sets:(8)V0=i∈V:yi=0V1=i∈V:yi=1namely, V0 (resp., V1) is the set of deactivated (resp., activated) entities of y.Additionally, let us now consider the following sets contained inAGV0:(9)P0=i∈V:∃j∈V0such  thati,j∈E,i=πr,j=πsands<rQ0=i∈V:∃j∈V0such  thati,j∈E,i=πr,j=πsands>rIn other words, each element i belonging to P0 (resp., Q0) is adjacent to a vertex j∈V0 which is updated, according the order expressed in π, before (resp., after) i.Similarly forV1, we consider the sets P1 and Q1 contained in AGV1:(10)P1=i∈V:∃j∈V1such  thati,j∈E,i=πr,j=πsands<rQ1=i∈V:∃j∈V1such  thati,j∈E,i=πr,j=πsands>rLastly, let us consider W⊆V (resp., W′⊆V) the set of entities such that the corresponding variables appear in the Boolean operator, maxterm or minterm, in direct (resp., complemented) form. These sets W and W′ are such that W′=Wc.


## 3. Main Results

In [43], the study of predecessors is divided into four specific problems:(i)
Predecessor existence (PRE).(ii)
Predecessor uniqueness (UPRE).(iii)
Predecessors coexistence (APRE).(iv)
Number of predecessors of a given state (#PRE).We will start solving the first of these problems. We will also provide a characterization of GOE points in the context of SDS on maxterm and minterm Boolean functions. Therefrom, some results will be also reached which will allow us to solve the rest of the problems in the previous list.The next theorem provides us with a characterization of GOE points in terms of sufficient and necessary conditions, finding a particular predecessor of a specific global state of the variables in the context of a SDS, when it exists.Theorem 3.
LetG,MAX,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the maxterm MAX. Then, a configuration y has a predecessor if, and only if, the state x defined as follows is such that MAXx=y:(i)
For every entityi∈V0∪P0
(a)
xi=0 if i∈W,(b)
xi=1 if i∈W′.(ii)
For every entityi∈V0∪P0c
(a)
xi=1 if i∈W,(b)
xi=0 if i∈W′.Proof.
It must only be shown that this condition is necessary for the existence of a predecessor. For this purpose, let us see that if there is a predecessor ofy, x^=x^1,…,x^n, then x defined as in this theorem is also a predecessor of y.
Thus, ifi∈V0∪P0, it must be(i)
x^i=0=xi if i∈W,(ii)
x^i=1=xi if i∈W′;
otherwiseyi=1 if i∈V0 or yj=1 for some j∈AG∗i∩V0 (those ones that update before i) if i∈P0.
Suppose, by reduction to the absurd, thatx is not a predecessor of y. Let i∈V be the first entity, according to the order established by π, such that xi does not update to yi. It must be i∈V0∪P0, because the entities in V0∪P0c⊆V1 update to the activated state because of their own state values in x.
Ifi∈P0∖V0⊆V1, let us analyze the possible state of the entities belonging to AGi:(i)
Sincei is the first entity not updating to the state given by yi=1, then ∀j∈AG∗i with i=πr, j=πs, and s<r, the entity j has updated to the state given by yj, the same as for x^,(ii)
xi=x^i,(iii)
∀j∈AG∗i with i=πr, j=πs, and s>r,
(a)
ifj∈P0∪V0, then xj=x^j,(b)
ifj∈P0∪V0c, then xj=1 if j∈W or xj=0 if j∈W′.
Sincex^i updates to yi=1, xi must also do it, but this is a contradiction and, consequently, i∉P0∖V0.
Thereforei∈V0. In this situation,(i)
Sincei is the first entity not updating to the state given by yi=0, then ∀j∈AG∗i with i=πr, j=πs, and s<r, the entity j has updated to the state given by yj, the same as for x^,(ii)
xi=x^i,(iii)
∀j∈AG∗i with i=πr, j=πs, and s>r, the entity j∈P0, and so xj=0 if j∈W or xj=1 if j∈W′.
Sincex^i updates to yi=0, xi must also do it, which is a contradiction and, consequently, i∉V0.
Therefore, there cannot existi∈V like that and x updates to y.Dually, we have the following.Theorem 4.
LetG,MIN,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the minterm MIN. Then, a configuration y has a predecessor if, and only if, the state x defined as follows is such that MINx=y:(i)
For every entityi∈V1∪P1
(a)
xi=1 if i∈W,(b)
xi=0 if i∈W′.(ii)
For every entityi∈V1∪P1c
(a)
xi=0 if i∈W,(b)
xi=1 if i∈W′.Theorems3 and 4 solve the PRE problem for SDS on maxterm and minterm Boolean functions as evolution operators, respectively, and allow us to establish the following characterization of the GOE points of these systems.Corollary 5.
LetG,MAX,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the maxterm MAX. Then, a configuration y is a GOE point of the system if, and only if, the state x defined as in Theorem 3 is such that MAXx≠y.Corollary 6.
LetG,MIN,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the minterm MIN. Then, a configuration y is a GOE point of the system if, and only if, the state x defined as in Theorem 4 is such that MINx≠y.Next, we provide sufficient conditions of GOE point.Corollary 7.
LetG,MAX,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the maxterm MAX. If a global state y is such that Q0∩V0∩W′≠∅, then y is a GOE point.Proof.
IfQ0∩V0∩W′≠∅, there is an entity i∈V0 whose corresponding variable in MAX appears in complemented form and with an adjacent entity j∈V0 updating after it. In this situation, the configuration y cannot be obtained as the update of another global state x because the evolution of the entity i to the deactivated state makes it impossible the posterior update of the entity j to this state.Corollary 8.
LetG,MAX,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the maxterm MAX. If a global state y is such that Q0∩V0c∩W≠∅, then y is a GOE point.Proof.
IfQ0∩V0c∩W≠∅, there is an entity i∈V1 whose corresponding variable in MAX appears in direct form and with an adjacent entity j∈V0 updating after it. The proof finishes reasoning as in Corollary 7.And dually, we have the following.Corollary 9.
LetG,MIN,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the minterm MIN. If a global state y is such that Q1∩V1∩W′≠∅, then y is a GOE point.Corollary 10.
LetG,MIN,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the minterm MIN. If a global state y is such that Q1∩V1c∩W≠∅, then y is a GOE point.From Corollary7 (resp., Corollary 9), it can be deduced that a configuration with two adjacent complemented vertices with state value 0 (resp., 1) is a GOE point of a G,MAX,π-SDS (resp., G,MIN,π-SDS). Actually, when MAX=NAND (resp., MIN=NOR), they are the only GOE points of the system.Indeed, if a configurationy of G,NAND,π-SDS is such that yi=yj=0 implies that {i,j}∉E, then y has a predecessor given by(i)
xi=1 if i∈V0∪P0,(ii)
xi=0 if i∈V0∪P0c.Additionally, since in such kind of systems any configuration reaches a periodic orbit at a maximum of one iteration (see [36]), we have the following.Proposition 11.
LetG,NAND,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the maxterm NAND. Then the GOE points of the system are the configurations such that there are two adjacent vertices i,j∈V with xi=xj=0. Furthermore, the other configurations belong to periodic orbits.And dually, we have the following.Proposition 12.
LetG,NOR,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the minterm NOR. Then the GOE points of the system are the configurations such that there are two adjacent vertices i,j∈V with xi=xj=1. Furthermore, the other configurations belong to periodic orbits.From Proposition11 (and, dually, from Proposition 12), we can see that the pattern of the parallel update shown in [31] for a MAX-PDS over a dependency graph G=V,E, with V={1,…,n} and n≥2, whereby a configuration with only one activated entity has no predecessors, is broken in the case of the sequential update, as shown in the following example.Example 13.
In the case of the SDS defined by(i)
G={{1,2},{{1,2}}},(ii)
MAX=x1′∨x2′,(iii)
π=1∣2,
the configurationy=0,1 is not a GOE point because x=1,1 is its predecessor.In view of these results, we can state the following corollaries about the number of GOE points in a SDS.Corollary 14.
LetG,MAX,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the maxterm MAX, with V={1,…,n} and n≥2. Then, the number of GOE points, #GOE, is such that 1≤#GOE≤2n-2. Moreover, these bounds are the best possible because they are reachable.Proof.
First, we will prove that any SDS withn≥2 has GOE points. Observe that, as n≥2, there exist two adjacent entities i and j with i updating before j. If i∈W, then a configuration with yi=1 and yj=0 has no predecessor; otherwise i∈W′ and the same occurs for a configuration with yi=yj=0.
In fact, the lower bound is reached, as shown in the example below. Let us consider theG,MAX,π-SDS defined by (i)
G={1,2},{{1,2}}.(ii)
MAX=x1′∨x2′.(iii)
π=1∣2.
In this case,0,0 is a GOE of the system and the rest of states belong to a 3-cycle, as can be checked in Figure 1.
On the other hand,y=1,…,1 is never a GOE of the system, because the state x defined as follows is its predecessor: (i)
xi=1 if i∈W,(ii)
xi=0 if i∈W′.
Also, there is always another point with a predecessor, because ifx¯ is defined as(i)
x¯i=0 if i∈W,(ii)
x¯i=1 if i∈W′
thenx¯ updates to a state y¯ such that y¯1=0.
As shown in the example below, this upper bound is also reached. Let us consider the followingG,MAX,π-SDS, determined by(i)
G={1,2},{{1,2}}.(ii)
MAX=x1∨x2′.(iii)
π=1∣2.
The phase diagram of this system is shown in Figure2.Figure 1
Phase diagram of the system.Figure 2
Phase diagram of the system.Remark 15.
In Corollary14, n≥2 has been imposed. This is necessary because a G,MAX,π- SDS with n=1 has 2 fixed points, if W′=∅, or one 2-cycle, if W=∅. That is, it has not GOE points in any case.And dually, we have the following.Corollary 16.
LetG,MIN,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the minterm MIN, with V={1,…,n} and n≥2. Then, the number of GOE points, #GOE, is such that 1≤#GOE≤2n-2. Moreover, these bounds are the best possible because they are reachable.In Theorem3, a constructive proof about the existence of a predecessor is shown. The structure of such a predecessor exposed in that result inspires the following result.Corollary 17.
LetG,MAX,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the maxterm MAX. If a configuration y has a predecessor x, the structure of such a predecessor is as follows:(i)
Ifyi=0, for every entity j∈AGi, with i=πr and j=πs:
(a)
Ifi=j or r<s:
(1)
xj=0 if j∈W, or(2)
xj=1 if j∈W′.(b)
Ifr>s:
(1)
yj=0 if j∈W, or(2)
yj=1 if j∈W′.(ii)
Ifyi=1, there exists an entity j∈AGi such that if i=πr and j=πs, at least one of the following conditions is accomplished:
(a)
i=j or r<s, and:
(1)
xj=1 if j∈W, or(2)
xj=0 if j∈W′.(b)
r>s, and:
(1)
yj=1 if j∈W, or(2)
yj=0 if j∈W′.Proof.
On the one hand, ifyi=0 and there is j∈AGi such that the conditions shown are not satisfied in this case, the entity i will update to the activated state due to this adjacent entity j, which is a contradiction. On the other hand, if yi=1 and ∀j∈AGi these conditions are not satisfied, the entity i will update to the deactivated state, which is also a contradiction.Dually, we have the following.Corollary 18.
LetG,MIN,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the minterm MIN. If a configuration y has a predecessor x, the structure of such a predecessor is as follows:(i)
Ifyi=1, for every entity j∈AGi, with i=πr and j=πs:
(a)
Ifi=j or r<s:
(1)
xj=1 if j∈W, or(2)
xj=0 if j∈W′.(b)
Ifr>s:
(1)
yj=1 if j∈W, or(2)
yj=0 if j∈W′.(ii)
Ifyi=0, there exists an entity j∈AGi such that if i=πr and j=πs, at least one of the following conditions is accomplished:
(a)
i=j or r<s, and:
(1)
xj=0 if j∈W, or(2)
xj=1 if j∈W′.(b)
r>s, and:
(1)
yj=0 if j∈W, or(2)
yj=1 if j∈W′.In aMAX-SDS (resp., MIN-SDS), the entities whose state is deactivated (resp., activated) in y determine univocally their state and the state of their adjacent entities in P0 (resp., P1) in any predecessor x, if such a predecessor exists. However, for any entity whose state value is 1 (resp., 0) in y, it is only necessary the intervention of a timely adjacent entity, or itself, with the appropriate state in the moment of its update. This point is the key to solve the UPRE, APRE, and #PRE problems hereafter.The following theorems allow us to determine if, given a statey with a predecessor x, there are other configurations different from x such that they are also predecessors of y. Thus, the UPRE and APRE problems in the context of a SDS on maxterm and minterm Boolean functions as evolution operators are solved.Theorem 19 (solution to the APRE and UPRE problems for maxterm-SDS).
LetG,MAX,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the maxterm MAX. Let y be a configuration of the system such that it has a predecessor. Then, there is a unique predecessor if, and only if, there is not a predecessor of y belonging to the following set:(11)P=x^∈0,1n:∃i∈V0∪P0csuchthatx^i≠xiandx^j=xj∀j∈V∖ibeing x the predecessor of y described in Theorem 3.Proof.
Sincex defined as in Theorem 3 is such that x∉P, it must only be shown that this condition is sufficient for the existence of a unique predecessor. For this purpose, let us see that if there is a predecessor of y different from x, x¯=x¯1,…,x¯n, then there exists a state x^=x^1,…,x^n∈P such that x^ is also a predecessor of y.
Given thatx¯≠x and x¯ is a predecessor of y, by Corollary 17, there is an entity i0∈V0∪P0c such that x¯i0≠xi0. Let us take x^ as the only element of P such that x^i0≠xi0 (consequently, x^i0=x¯i0), and let us see that this state is a predecessor of y.
Suppose, by reduction to the absurd, thatx^ is not a predecessor of y. Let i∈V be the first entity, according to the order established by π, such that x^i does not update to yi. It must be i∈V0∪P0∪i0, because the entities in V0∪P0∪{i0}c⊆V1 update to the activated state because of their own state values in x^.
Ifi∈P0∖V0∪{i0}=P0∖V0⊆V1, let us analyze the possible state of the entities belonging to AGi:(i)
Sincei is the first entity not updating to the state given by yi=1, then ∀j∈AG∗i with i=πr, j=πs, and s<r, the entity j has updated to the state given by yj, the same as for x¯,(ii)
x^i=x¯i,(iii)
∀j∈AG∗i with i=πr, j=πs and s>r,
(a)
ifj∈P0∪V0∪{i0} then x^j=x¯j,(b)
ifj∈P0∪V0∪{i0}c then x^j=1 if j∈W or x^j=0 if j∈W′.
Sincex¯i updates to yi=1, x^i must also do it, but this is a contradiction and, consequently, i∉P0∖V0.
Ifi∈V0∖{i0}=V0, we have the following:(i)
Sincei is the first entity not updating to the state given by yi=0, then ∀j∈AG∗i with i=πr, j=πs and s<r, the entity j has updated to the state given by yj, the same as for x¯,(ii)
x^i=x¯i,(iii)
∀j∈AG∗i with i=πr, j=πs, and s>r, the entity j∈P0=P0∖{i0}, and so xj=0 if j∈W or xj=1 if j∈W′.
Sincex¯i updates to yi=0, x^i must also do it, which is a contradiction and, consequently, i∉V0.
Thereforei=i0. In this situation, we have the following:(i)
Sincei is the first entity not updating to the state given by yi=1 (i0∈V0∪P0c⊆V1), then ∀j∈AG∗i0 with i0=πr, j=πs, and s<r, the entity j has updated to the state given by yj, the same as for x¯,(ii)
x^i0=x¯i0,(iii)
∀j∈AG∗i0 with i0=πr, j=πs and s>r,
(a)
ifj∈P0∪V0 then x^j=x¯j,(b)
ifj∈P0∪V0c then x^j=1 if j∈W or x^j=0 if j∈W′.
Sincex¯i updates to yi=1, x^i must also do it, but this is also a contradiction and, consequently, i≠i0.
Therefore, there cannot existi∈V like that and x^ updates to y.Remark 20.
The previous result reduces an initial exponentially sized problem, the search of a particular configuration among the2n possible states of the system, into another one in which, at most, n cases must be analyzed. In this case, a short list of possible candidates is provided and the evaluation of the evolution operation only over the elements of this set provides the answer to the global problem of existence of a unique predecessor for a state y.And dually, we have the following.Theorem 21 (solution to the APRE and UPRE problems for minterm-SDS).
LetG,MIN,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the minterm MIN. Let y be a configuration of the system such that it has a predecessor. Then, there is a unique predecessor if, and only if, there is not a predecessor of y belonging to the following set:(12)P=x^∈0,1n:∃i∈V1∪P1csuchthatx^i≠xiandx^j=xj∀j∈V∖ibeing x the predecessor of y described in Theorem 4.These results respond to the question of the existence of more than one predecessor for a statey. The next step is to go deeper into this topic, getting the number of them. In the following results, we explain a method to obtain all the predecessors of y and, consequently, this number in order to solve the predecessor problem #PRE.Corollary 22.
LetG,MAX,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the maxterm MAX. Let y be a configuration and let us consider the following iterative process:(i)
Pn+1={y},(ii)
ifi∈V, then Pi={x∈{0,1}n:∃y¯∈Pi+1suchthatxj=y¯jifj≠πiandMAXAGπix=yπi}, being MAXAGπi the restriction of MAX over AGπi.
Then,P1 is the set of all the predecessors of y.Example 23.
Let us illustrate this procedure with a particular example, in order to clarify the notation. We consider theG,MAX,π- SDS defined by(i)
G={1,2,3},{{1,3},{2,3}}.(ii)
MAX=x1∨x2∨x3.(iii)
π=1∣2∣3.
The phase diagram of this system is shown in Figure3.
The set of predecessors of the configurationy=1,1,1 is(13)1,1,1,1,1,0,0,0,1,0,1,1,1,0,1Let us see that this set is obtained as P1 at the end of the iterative process starting with P4=1,1,1.
Firstly,P3 is obtained: since π3=3, the only configurations that can belong to P3 are 1,1,0 and 1,1,1. On the other side, since MAXAG31,1,0=MAXAG31,1,1=1=y3, it is P3=1,1,0,1,1,1.
Then, to obtainP2, since π2=2 and considering the elements in P3, the only configurations that can belong to P2 are 1,0,0, 1,1,0, 1,0,1, and 1,1,1. Now, MAXAG21,0,0=0≠y2 and MAXAG21,1,0=MAXAG21,0,1=MAXAG21,1,1=1=y2, so P2={1,1,0,1,0,1,1,1,1}.
Finally, sinceπ1=1 and knowing the set P2, the only configurations that can belong to P1 are 0,1,0, 1,1,0, 0,0,1, 1,0,1, 0,1,1, and 1,1,1. Now, MAX|AG10,1,0 is equal to 0≠y1, while MAXAG11,1,0, MAXAG10,0,1, MAXAG11,0,1, MAXAG10,1,1, and MAXAG11,1,1 are all equal to 1=y1.
Thus,P1={1,1,0,0,0,1,1,0,1,0,1,1,1,1,1}.Figure 3
Phase diagram of the system.Dually, we have the following.Corollary 24.
LetG,MIN,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the minterm MIN. Let y be a configuration and let us consider the following iterative process:(i)
Pn+1={y},(ii)
ifi∈V, then Pi={x∈{0,1}n:∃y¯∈Pi+1suchthatxj=y¯jifj≠πiandMINAGπix=yπi}, being MINAGπi the restriction of MIN over AGπi.
Then,P1 is the set of all the predecessors of y.These last procedures allow us to know all the predecessors of a statey in a SDS and, consequently, the number of them. Since this calculus depends on the particular graph, in the following results we give a bound for this number.Theorem 25.
LetG,MAX,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the maxterm MAX. Then, the number of predecessors of a given state y is upper bounded by 2#V0∪P0c. Moreover, this bound is the best possible because it is reachable.Proof.
From Theorem3 and Corollary 17, the states of the entities belonging to V0∪P0 in a possible predecessor of y are fixed. Since the state values of the rest of entities are either 0 or 1, a first upper bound for the number of predecessors is 2#V0∪P0c.
This upper bound is the best possible because it is reached in the following example. Let us consider theG,MAX,π-SDS defined by(i)
G={V,E}, with V={1,…,n}, n≥2, and E={{2,i}:i∈V∖{2}}.(ii)
MAX=x1′∨x2∨x3∨⋯∨xn.(iii)
π=1∣…∣n.
In this context, ify=0,1,…,1, then V0={1}, P0={2}, Q0=∅, and V1={2,…,n}.
In any predecessor,x, it must be x1=1 and x2=0, but, in this case, all the other choices for the states of the rest of entities generate predecessors of y.And dually, we have the following.Theorem 26.
LetG,MIN,π-SDS be a sequential dynamical system over a dependency graph G=V,E associated with the minterm MIN. Then, the number of predecessors of a given state y is upper bounded by 2#V1∪P1c. Moreover, this bound is the best possible because it is reachable.


## 4. Conclusions and Future Research Directions

The results here obtained for SDS in relation to the predecessors existence problems and GOE not only suppose an algebraic solution for such problems, but also constitute a generalization to those achieved for PDS recently.On the other hand, these results could reveal interesting interpretations for those phenomena modeled by these SDS, what gives an idea of their relevance.Taking into account that the interactions among elements of a phenomenon could be (only) unidirectional, these results encourage us to know what happens for SDS over directed graphs as a future research direction.



---

*Source: 6280960-2019-03-07.xml*