Predecessors and Gardens of Eden in sequential dynamical systems over directed graphs

Graph dynamical systems (GDS) constitute mathematical formalizations of situations where there are several elements related among them, whose interactions determine the evolution of their states and, consequently, the evolution of the state of the whole system. In this sense, there are four important sets which can be distinguished in these kinds of systems: the set of entities, the set of their relations, the set of states of the elements, the set of interaction modus of related elements, and the set reflecting the order in which the iterations happen in a unit of time.

The set of entities together with the set of relations are formalized by a graph; the set of states is commonly a Boolean algebra; the iterations are given by local (Boolean) functions (f_i)_{i∈{1,…,n}} that act on related elements; the set reflecting the order is usually formalized by a permutation. Observe that, in this situation, the state space of the dynamical system consists of state vectors of the form (x₁, …, x_n) which have the states of the elements as coordinates; the evolution operator F is constructed considering all the local functions jointly; and the time is discrete.

When the number of elements and their states are finite (and, as a consequence, the number of relations is finite, since the graph is at most complete), it is said that the GDS is finite (FGDS). When the states of the elements belong to a Boolean algebra (and, consequently, the local functions are Boolean), it is said that the GDS is a Boolean one (BGDS). When all the interactions occur at the same time the GDS is called synchronous or parallel; otherwise, the GDS is called asynchronous or sequential (in particular, if more than one elements interact at the same time, but not all of them, the GDS is said to be mixed or block-sequential). In the context of BGDS, for short, parallel systems are denoted by PDS, while sequential systems by SDS, as done here and in the majority of related works [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 24, 25]

When the interactions are unidirectional, we can formalize the elements and their relations with a (dependency) directed graph D = (V, A). In this digraph D, each initial node of every arc entering a vertex i ∈ V represents an influencing element with respect to i, that is, the vertices that intervene in its updating. As shown in [2, 8, 9], the dynamics of GDS over undirected graphs can be very different from the dynamics over directed ones. This motivates the study in both contexts separately to extract such differences, as done in [2, 5, 6, 8, 9, 22, 23, 26, 27]. Thus, in this work, once the situation in the undirected context is known [7], we deal with the predecessors existence problems for SDS over directed graphs (SDDS).

The abbreviations GDS, FGDS, BGDS, PDS, SDS, PDDS, SDDS, 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.

For our purposes, we consider that the digraph D = (V, A) could be arbitrary, although it cannot have more arcs than the corresponding complete digraph. Without loss of generality, we suppose that D is weakly connected. On the other hand, the set of states of the elements is the basic Boolean algebra {0, 1}, while the local functions are restrictions of a maxterm (or minterm) Boolean function.

As in [6], for each entity i ∈ V, we consider the set I_D(i) ⊆ V given by

IDi={j∈V:j,i∈A}∪{i},$$\begin{array}{} \displaystyle I_{D}\left(i\right) = \{j\in V:\left(j, i\right)\in A\}\cup\{i\}, \end{array}$$

that is, the set of all the entities influencing i in its update. Similarly, for W ⊆ V, we denote

IDW=⋃i∈WIDi∪W.$$\begin{array}{} \displaystyle I_{D}\left(W\right) = \bigcup_{i\in W} I_{D}\left(i\right)\cup W. \end{array}$$

Also, we consider the sets:

ID∗i=IDi∖{i},$$\begin{array}{} \displaystyle I_{D}^{\ast}\left(i\right) = I_{D}\left(i\right)\setminus\{i\}, \end{array}$$

ID∗W=IDW∖W.$$\begin{array}{} \displaystyle I_{D}^{\ast}\left(W\right) = I_{D}\left(W\right)\setminus W. \end{array}$$

Let D = (V, A) be a digraph with V = {1, …, n}, π = (π₁, …, π_n) a permutation on V and

F,π=Fπn∘…∘Fπ1:{0,1}n→{0,1}n,$$\begin{array}{} \displaystyle \left[F, \pi\right] = F_{\pi_{n}}\circ\ldots\circ F_{\pi_{1}}:\{0, 1\}^{n}\rightarrow\{0, 1\}^{n}, \end{array}$$

a Boolean function such that F_πi : {0, 1}ⁿ → {0, 1}ⁿ updates the state of the entity π_i ∈ V by considering the state values of the entities belonging to I_D(i), and keeping the other states unaltered. These elements define a SDDS that will be denoted by [D, F, π]-SDDS or by F–SDDS when indicating the digraph and permutations was not necessary. In particular, in this paper, a SDDS whose local functions come from the restrictions of a maxterm (resp. minterm) will be denoted by MAX-SDDS (resp. MIN-SDDS).

The orbits in a SDDS are finite sequences of state vectors:

(x1,…,xn),F(x1,…,xn),FF(x1,…,xn),…,F(n)(x1,…,xn),…,$$\begin{array}{} \displaystyle (x_1, \dots, x_n), F(x_1, \dots, x_n), F\left(F(x_1, \dots, x_n)\right), \dots, F^{(n)}(x_1, \dots, x_n), \dots, \end{array}$$

and they can be represented all together as another directed graph, where each node corresponds to a state vector and each arc means that its final node is the image of the initial node by the global operator F. This representation is called the phase diagram or transition diagram of the SDDS. It is also called phase space or phase portrait in consonance with the general theory of dynamical systems.

Analyzing the dynamics of a SDDS means to give a description of its transition diagram. As the state space is finite, a SDDS can only present periodic orbits or eventually periodic orbits. In this context, one could think that any orbit could be computed directly using adequate algorithms [11, 19]. However, describing the phase diagram could result a complexity problem. On the other hand, the results obtained for a particular SDDS, cannot be inferred to a general one. Thus, to obtain information about the transition diagrams of SDDS, we should analyze them algebraically in relation to their four fundamental sets.

When F(x₁, …, x_n) = (y₁, …, y_n), then the state (vector) (x₁, …, x_n) is called a predecessor of (y₁, …, y_n). If there is no predecessor for a state vector (y₁, …, y_n), then (y₁, …, y_n) is called a Garden-of-Eden (GOE) state of the system. We can assume that every eventually periodic orbit of a SDDS is part of another eventually one whose initial state has no predecessors. Thus, analyzing predecessors and GOE becomes a key question in order to describe the transition diagram of a SDDS.

This analysis can be carried out by studying, for any state vector, the existence of predecessors, the uniqueness or coexistence of predecessors, and, in case of having more than one predecessor, the maximum number of them (see [5, 6, 7, 15, 16]).

In some previous works the analysis have been performed from the point of view of complexity (see [15, 16, 17, 21, 22, 23, 28]). Particularly, in [15], it is shown that the existence of predecessors is an NP-complete problem in the case of some special graphs, where the evolution operator is either the simplest maxterm OR (resp. minterm AND) or other symmetric Boolean operator. In [16], Barret et al. present general techniques that characterize the computational complexity of the predecesor problems, so generalizing the results in [21] or [28]. In the recent work [22], the authors study the computational complexity of generalized t-predecessor problems an t-GOE for some particular cases of PDS corresponding to a variety of sets of permissible update functions as well as for polynomially bounded t. The work [23] is the counterpart corresponding to PDS over directed graphs (PDDS). On the other hand, in relation to GOE problems, one can find sufficient conditions of non-existence of GOE in [14], which extend the results in [24], for invertible systems.

From the algebraic perspective, we solved the four predecessor problems for PDS whose updating is performed by means of a general maxterm or minterm Boolean function in [5], and for its counterpart over directed graphs PDDS in [6]. Recently, we have also solved these four problems and characterize the GOE states for SDS on these Boolean functions in [7].

In view of these previous works, here we extend our results to the case of SDS over directed graphs. In particular, changing slightly the arguments in the demonstrations, we get results, similar as those for SDS, for the predecessor and GOE problems in SDDS. The results here obtained not only suppose an algebraic solution for such problems in SDDS, but they also complete those achieved for PDS in [5], for PDDS in [6], and for SDS in [7].

This paper is organized as follows. Section 2 is devoted to studying the existence of predecessor and to characterize the GOE states (algebraically), giving bounds for the number of GOE in a SDDS. In addition, we provide conditions for the uniqueness and coexistence of predecessors, and, in case of coexistence, we provide upper bounds for the number of them. In Section 3, we comment the main conclusions and the related open research directions.

Given a generic state (vector) (y₁, …, y_n) of a [D, F, π]-SDDS over the directed graph D = (V, A), as in [7], we will consider the following subsets of V, which will be useful throughout this document:

V0={i∈V:yi=0},V1={i∈V:yi=1}.$$\begin{array}{} \displaystyle V_{0} = \{i\in V:y_{i} = 0\}, \\ V_{1} = \{i\in V:y_{i} = 1\}. \end{array}$$

Also inspired by the considerations in [7], we will consider the subsets of I_D(V₀) given by:

P0={i∈V:∃j∈V0suchthati,j∈A,i=πr,j=πsands<r}Q0={i∈V:∃j∈V0suchthati,j∈A,i=πr,j=πsands>r}.$$\begin{array}{} \displaystyle P_{0} = \{i\in V:\exists j\in V_{0}\, {\rm such}\, {\rm that}\, \left(i, j\right)\in A, \, i = \pi_{r}, \,\, j = \pi_{s}\, {\rm and}\, s \lt r\}\\\\ \displaystyle Q_{0} = \{i\in V:\exists j\in V_{0}\, {\rm such}\, {\rm that}\, \left(i, j\right)\in A, \, i = \pi_{r}, \,\, j = \pi_{s}\, {\rm and}\, s \gt r\}. \end{array}$$

Observe that, although the notation employed is the same as in [7], the meaning of each of these two subsets is different from the one with the same notation in [7]. Indeed, in contrast with the case of SDS in [7], now, each element i belonging to P₀ (resp. Q₀) is influencing a vertex j ∈ V₀ which is updated, according the order expressed in π, before (resp. after) i. Nevertheless, we use the same notation because they are used in the proofs of the results in the same sense.

For V₁, similarly, we consider the subsets of I_D(V₁) given by:

P1={i∈V:∃j∈V1suchthati,j∈A,i=πr,j=πsands<r}Q1={i∈V:∃j∈V1suchthati,j∈A,i=πr,j=πsands>r}$$\begin{array}{} \displaystyle P_{1} = \{i\in V:\exists j\in V_{1}\, {\rm such}\, {\rm that}\, \left(i, j\right)\in A, \, i = \pi_{r}, \,\, j = \pi_{s}\, {\rm and}\, s \lt r\}\\\\ \displaystyle Q_{1} = \{i\in V:\exists j\in V_{1}\, {\rm such}\, {\rm that}\, \left(i, j\right)\in A, \, i = \pi_{r}, \,\, j = \pi_{s}\,{\rm and}\, s \gt r\} \end{array}$$

As usually done, we will denote by 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. Observe that W^′ = W^c.

Similarly to the case of SDS [7], we can solve the existence predecessor problem and give a characterization of GOE states for SDDS, thanks to a fundamental vector state that can be construct from any given state (y₁, …, y_n). When existing, this fundamental state is a predecessor.

Dually, we have:

Apart from the characterization, as done in [7] for SDS, we can also provide sufficient conditions to determine if a given state is a GOE of a MAX-SDDS (resp. MIN-SDDS). The sufficient conditions for SDDS “notationally” coincide with the ones given for SDS, although the meaning of the subset Q₀ (resp. Q₁) involved is different in this context.

For the case of MIN-SDDS, we dually have:

With the same considerations, one can obtain exactly the same bounds for the number of GOE in SDDS, as those found in SDS in [7]. Since, in this case, the proof needs some arguments different from the ones in the the case of SDS (see [7]), we include it.

Proof

In this proof, we demonstrate only the case of a MAX-SDDS. The case of a MIN-SDDS is then obtained automatically by duality.

First of all, we will prove that, for a MAX-SDDS with n ≥ 2 there is always a GOE point. Effectively, if there exists an arc from an entity i towards an entity j, with i updating before j, then:

if i ∈ W, then a state vector with y_i = 1 and y_j = 0 cannot be obtained under updating of other state (x₁, …, x_n),

if i ∈ W^′, then a state vector with y_i = y_j = 0 cannot be obtained under updating of other state (x₁, …, x_n).

Otherwise, if this arc does not exist, each arc is such that its initial vertex updates after its final vertex, according to the order of updating, that hereafter we denominate π. Thus, the last updating vertex π_n is not influenced by another one in its update and, in any predecessor of a vector state with y_πn = 1, π_n must be activated if π_n ∈ W, or deactivated if π_n ∈ W^′. Since the dependency digraph is weekly connected, there exists k ∈ V such that (π_n, k) is one of its arcs and, therefore, x_k = 0 and x_πn = 1 cannot be obtained after the update of any vector state.

This lower bound is reached in the following example. Let [D, MAX, π]-SDDS the SDDS given by:

D = ({1, 2}, {(1, 2)}).

MAX = x1′∨x2′.$\begin{array}{} \displaystyle x_{1}^{\prime}\vee x_{2}^{\prime}. \end{array}$

π = 1|2.

In this case, (0, 0) is the unique GOE of the system, as can be check in its phase diagram of Figure 1:

Fig. 1

Observe that the condition n ≥ 2 has to be considered since, as can be easily checked, when n = 1, then MAX-SDDS has 2 fixed points if W^′ = ∅, or one 2-cycle if W = ∅. That is, when n = 1, MAX-SDDS has no GOE states.

Secondly, we will demonstrate that 2ⁿ − 2 is an upper bound for the number of GOE of a MAX-SDDS. Observe that the vector state y = (1, …, 1) is never a GOE of the system, because it has a predecessor (x₁, …, x_n) defined as follows:

x_i = 1 if i ∈ W, and

x_i = 0 if i ∈ W^′.

In addition, there is always another state with a predecessor because, if x is defined as

x_i = 0 if i ∈ W, and

x_i = 1 if i ∈ W^′,

then x updates to a state y such that y₁ = 0.

Finally, the upper bound is reached in the following example. Let us consider the following [D, MAX, π]-SDDS, determined by:

D = ({1, 2}, {(1, 2), (2, 1)}).

MAX = x₁ ∨ x2′$\begin{array}{} \displaystyle x_{2}^{\prime} \end{array}$.

π = 1|2.

The phase diagram of this system is:

Fig. 2

The following theorems allow us to determine if, given a state (y₁, …, y_n) with fundamental predecessor (x₁, …, x_n) as in Theorem 1 or Theorem 2, there exists other predecessor different from (x₁, …, x_n). Hence, they solve the problems concerning uniqueness and coexistence of predecessors in the context of a SDDS on maxterm and minterm Bolean. We do not include the proofs that can be easily obtain, following the same arguments given in [7] in the context of SDS.

Dually, we can state:

As in the case of SDS, for SDDS one could easily obtain theoretically the set of all predecessors of a given state (see [7]). This set allows us to know all the predecessors of a state (y₁, …, y_n) in a SDDS and, consequently, the number of them. But, this number depends on the digraph considered. However, we can give an upper bound for such a number. As we have developed our previous results, it is not strange that this bound was the same as in the case of SDS. In fact, the demonstration for SDDS could be written following the same arguments as in [7] for SDS. In this sense, we can state the following theorem, where the symbol # preceding a set denotes the cardinality of the set:

This upper bound is the best possible because it could be reached, as occurs in the following example.

In this work, we extend the existing results for predecessor problems and GOE of SDS with a maxterm or minterm Boolean function as evolution operator by solving these problems in the case of SDS over directed graphs. Actually, this work totally completes the results on this problems for homogeneous FGDS on maxterm or minterm Boolean functions.

As in our previous works, the main difference with respect to other related works is that, instead of treating the problems from the point of view of computational complexity, we have treated and solved them algebraically.

The results in this work open some future research directions. Among them, the ideas in this paper could help to obtain results in the context of FGDS on independent local maxterm or minterm Boolean functions over directed and undirected dependency graphs.