1. bookVolume 3 (2018): Issue 2 (July 2018)
Journal Details
License
Format
Journal
First Published
01 Jan 2016
Publication timeframe
2 times per year
Languages
English
access type Open Access

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

Published Online: 31 Dec 2018
Page range: 593 - 602
Received: 12 Oct 2018
Accepted: 31 Dec 2018
Journal Details
License
Format
Journal
First Published
01 Jan 2016
Publication timeframe
2 times per year
Languages
English
Abstract

In this work, we deal with the predecessors existence problems in sequential dynamical systems over directed graphs. The results given in this paper extend those existing for such systems over undirected graphs. In particular, we solve the problems on the existence, uniqueness and coexistence of predecessors of any given state vector, characterizing the Garden-of-Eden states at the same time. We are also able to provide a bound for the number of predecessors and Garden-of-Eden state vectors of any of these systems.

Keywords

MSC 2010

Introduction

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 (fi)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 (x1, …, xn) 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 iV 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 iV, we consider the set ID(i) ⊆ V given by

IDi={jV:j,iA}{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 WV, we denote

IDW=iWIDiW.$$\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:

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

IDW=IDWW.$$\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}, π = (π1, …, πn) a permutation on V and

F,π=FπnFπ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}n → {0, 1}n updates the state of the entity πiV by considering the state values of the entities belonging to ID(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(x1, …, xn) = (y1, …, yn), then the state (vector) (x1, …, xn) is called a predecessor of (y1, …, yn). If there is no predecessor for a state vector (y1, …, yn), then (y1, …, yn) 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.

Main results

Given a generic state (vector) (y1, …, yn) 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={iV:yi=0},V1={iV: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 ID(V0) given by:

P0={iV:jV0suchthati,jA,i=πr,j=πsands<r}Q0={iV:jV0suchthati,jA,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 P0 (resp. Q0) is influencing a vertex jV0 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 V1, similarly, we consider the subsets of ID(V1) given by:

P1={iV:jV1suchthati,jA,i=πr,j=πsands<r}Q1={iV:jV1suchthati,jA,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 WV (resp. WV) 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 = Wc.

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 (y1, …, yn). When existing, this fundamental state is a predecessor.

Theorem 1

A state (y1, …, yn) of a MAX-SDDS has predecessors if, and only if, the state (x1, …, xn), defined as

iV0P0,xi=0ifiWxi=1ifiWiV0P0c,xi=1ifiWxi=0ifiW$$\begin{array}{} \displaystyle \forall i\in V_{0}\cup P_{0}, ~~~~~ \left\{\begin{array}{ll} x_{i} = 0 ~ if ~i\in W\\ x_{i} = 1 ~ if ~i\in W^{\prime} \end{array}\right.\\\\ \forall i\in \left(V_{0}\cup P_{0}\right)^{c}, ~ \left\{\begin{array}{ll} x_{i} = 1~ if~ i\in W\\ x_{i} = 0~if~ i\in W^{\prime} \end{array}\right. \end{array}$$

verifies MAX(x1, …, xn) = (y1, …, yn).

Proof

To do this proof, we only need to follow similar arguments to those of Theorem 1 in [7], but now using the new subset P0, defined above, and considering influencing entities instead of adjacent ones. For the sake of completeness, we write the complete demonstration below.

Observe that we only need to prove the direct implication, since the reciprocal is obviously true. Thus, we only need to prove that if a (vector) state (y1, …, yn) of a MAX-SDDS has predecessors, then the state (x1, …, xn) defined above is one of these predecessors. Effectively, suppose that = (1, …, n) is a predecessor of (y1, …, yn). Thus,

iV0P0,x~i=0=xiif iWx~i=1=xiif iW$$\begin{array}{} \displaystyle \forall i\in V_{0}\cup P_{0}, \left\{\begin{array}{ll} \widetilde{x}_{i} = 0 = x_{i} ~ \mbox{if } i\in W\\ \widetilde{x}_{i} = 1 = x_{i} ~ \mbox{if } i\in W^{\prime} \end{array}\right. \end{array}$$

Secondly, suppose, that (x1, …, xn) defined as above is not a predecessor of (y1, …, yn). Then, we can called iV to the first entity, according to the updating order, such that xi does not update to yi. Then, i must belong to V0P0, because any entity in (V0P0)cV1 updates to the activated state.

If iP0V0V1, we have:

Since xi is the first state not updating to yi = 1, then ∀ jID$\begin{array}{} \displaystyle I_{D}^{\ast} \end{array}$(i) with i = πr, j = πs and s < r, xj updates to yj, as occurs for ,

xi = i, and

jID$\begin{array}{} \displaystyle I_{D}^{\ast} \end{array}$(i) with i = πr, j = πs and s > r,

xj=x~jif jP0V0xj=1if jP0V0cand jWxj=0if jP0V0cand jW$$\begin{array}{} \displaystyle \left\{\begin{array}{llll} x_{j} = \widetilde{x}_{j} ~\mbox{if } j\in P_{0}\cup V_{0} \\ x_{j} = 1 ~~~\mbox{if } j\in\left(P_{0}\cup V_{0}\right)^{c} ~\mbox{and } j\in W\\ x_{j} = 0 ~~~\mbox{if } j\in\left(P_{0}\cup V_{0}\right)^{c} ~\mbox{and } j\in W^{\prime} \end{array}\right. \end{array}$$

Since i updates to yi = 1, so does xi, what is a contradiction. Hence, iP0V0. Thus, we can conclude that iV0. At this point,

Since i is the first entity not updating to the state given by yi = 0, ∀ jID$\begin{array}{} \displaystyle I_{D}^{\ast} \end{array}$(i) with i = πr, j = πs and s < r, the entity j has updated to the state given by yj, the same as for , and

xi = i, and

jID$\begin{array}{} \displaystyle I_{D}^{\ast} \end{array}$(i) with i = πr, j = πs and s > r, the entity jP0, so xj = 0 if jW or xj = 1 if jW.

Since i updates to yi = 0, then xi must also do it, which is a contradiction. Hence, iV0.

As a consequence, there does not exist iV, such that xi does not update to yi, i.e., (x1, …, xn) updates to (y1, …, yn).□

Dually, we have:

Theorem 2

A state (y1, …, yn) of a MIN-SDDS has predecessors if, and only if, the state (x1, …, xn), defined as

iV1P1,xi=1ifiWxi=0ifiWiV1P1c,xi=0ifiWxi=1ifiW$$\begin{array}{} \displaystyle \begin{array}{ll} \forall i\in V_{1}\cup P_{1},~~~~ \left\{\begin{array}{ll} x_{i} = 1~ if~ i\in W\\ x_{i} = 0 ~if~ i\in W^{\prime} \end{array}\right. \\\\\\ \displaystyle \forall i\in \left(V_{1}\cup P_{1}\right)^{c}, \left\{\begin{array}{ll} x_{i} = 0~if~ i\in W\\ x_{i} = 1~if~ i\in W^{\prime} \end{array}\right. \end{array} \end{array}$$

verifies MIN(x1, …, xn) = (y1, …, yn).

Remark 1

Theorem 1 (resp. Theorem 2) allows us to deduce the non-existence of predecessors for SDDS on maxterm (resp. minterm) Boolean functions too, so providing a characterization of the GOE states of these systems. In particular, a given state (y1, …, yn) is a GOE of MAX-SDDS (resp. MIN-SDDS) if, and only if, there does not exist a fundamental predecessor (x1, …, xn), as defined in Theorem 1 (resp. Theorem 2).

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 Q0 (resp. Q1) involved is different in this context.

Corollary 1

If a state (y1, …, yn) of a MAX-SDDS verifies that (Q0V0) ∩ W ≠ ∅ or (Q0V0c$\begin{array}{} \displaystyle V_{0}^{c} \end{array}$) ∩ W ≠ ∅, then (y1, …, yn) is a GOE state.

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

Corollary 2

If a global state (y1, …, yn) of a MIN-SDDS verifies that (Q1V1) ∩ W ≠ ∅ or (Q1V1c$\begin{array}{} \displaystyle V_{1}^{c} \end{array}$) ∩ W ≠ ∅, then (y1, …, yn) is a GOE state.

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.

Corollary 3

The number of GOE states, #GOE, in a MAX-SDDS or MIN-SDDS is such that 1 ≤ #GOE ≤ 2n − 2. Moreover, these bounds are the best possible because they are reachable.

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 iW, then a state vector with yi = 1 and yj = 0 cannot be obtained under updating of other state (x1, …, xn),

if iW, then a state vector with yi = yj = 0 cannot be obtained under updating of other state (x1, …, xn).

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 πnW, or deactivated if πnW. Since the dependency digraph is weekly connected, there exists kV such that (πn, k) is one of its arcs and, therefore, xk = 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 = x1x2.$\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

Phase diagram of the system.

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 2n − 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 (x1, …, xn) defined as follows:

xi = 1 if iW, and

xi = 0 if iW.

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

xi = 0 if iW, and

xi = 1 if iW,

then x updates to a state y such that y1 = 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 = x1x2$\begin{array}{} \displaystyle x_{2}^{\prime} \end{array}$.

π = 1|2.

The phase diagram of this system is:

Fig. 2

Phase diagram of the system.

The following theorems allow us to determine if, given a state (y1, …, yn) with fundamental predecessor (x1, …, xn) as in Theorem 1 or Theorem 2, there exists other predecessor different from (x1, …, xn). 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.

Theorem 3

A state (y1, …, yn) of a MAX-SDDS has a unique predecessor if, and only if, there is not a predecessor of (y1, …, yn) belonging to the following set:

{x~{0,1}n:iV0P0csuchthatx~ixiandx~j=xjjV{i}}$$\begin{array}{} \displaystyle \{\widetilde{x}\in\{0, 1\}^{n}:\exists\, i\in\left(V_{0}\cup P_{0}\right)^{c}\, such\, that\, \widetilde{x}_{i}\neq x_{i}\, and\, \widetilde{x}_{j} = x_{j}\, \forall j\in V\setminus\{i\}\} \end{array}$$

Dually, we can state:

Theorem 4

A state (y1, …, yn) of MIN-SDDS has a unique predecessor if, and only if, there is not a predecessor of (y1, …, yn) belonging to the following set:

{x~{0,1}n:iV1P1csuchthatx~ixiandx~j=xjjV{i}}$$\begin{array}{} \displaystyle \{\widetilde{x}\in\{0, 1\}^{n}:\exists\, i\in \left(V_{1}\cup P_{1}\right)^{c}\, such\, that\, \widetilde{x}_{i}\neq x_{i}\, and\, \widetilde{x}_{j} = x_{j}\, \forall j\in V\setminus\{i\}\} \end{array}$$

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 (y1, …, yn) 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:

Theorem 5

The number of predecessors of a given state (y1, …, yn) of a MAX-SDDS or a MIN-SDDS is upper bounded by 2#(V0P0)c. Moreover, this bound is the best possible because it is reachable.

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

Example 1

Let us consider the [D, MAX, π]-SDDS defined by:

D = {V, A}, withV = {1, …, n}, n ≥ 2, andA = {(2, i) : iV ∖ {2}} ∪ {(1, 2)}.

MAX = x1$\begin{array}{} \displaystyle x_{1}^{\prime} \end{array}$x2x3 ∨ ⋯ ∨ xn.

π = (1, …, n).

In this context, ify = (0, 1, …, 1) thenV0 = {1}, P0 = {2}, Q0 = ∅ andV1 = {2, …, n.

In any predecessor, (x1, …, xn), it must bex1 = 1 andx2 = 0, but, in this case, all the other choices for the states of the rest of entities generate predecessors of (y1, …, yn).

Conclusions and Future Research Directions

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.

Fig. 1

Phase diagram of the system.
Phase diagram of the system.

Fig. 2

Phase diagram of the system.
Phase diagram of the system.

N.L. Ackerman, C.E. Freer, Graph Turing Machines, Proceedings of WoLLIC 2017, LNCS Vol. 10388, 1–13, 2017.AckermanN.L.FreerC.E.Graph Turing MachinesProceedings of WoLLIC 2017, LNCS103881132017Search in Google Scholar

J.A. Aledo, L.G. Diaz, S. Martinez, J.C. Valverde, On the periods of parallel dynamical systems, Complexity 2017 (2017), Article ID 7209762, 6 pages. 10.1155/2017/7209762.AledoJ.A.DiazL.G.MartinezS.ValverdeJ.C.On the periods of parallel dynamical systemsComplexity20172017Article ID 7209762610.1155/2017/7209762Open DOISearch in Google Scholar

J.A. Aledo, L.G. Diaz, S. Martinez, J.C. Valverde, On periods and equilibria of sequential dynamical systems, Inf. Sci. 409–410 (2017) 27–34. 10.1016/j.ins.2017.05.002.AledoJ.A.DiazL.G.MartinezS.ValverdeJ.C.On periods and equilibria of sequential dynamical systemsInf. Sci.4094102017273410.1016/j.ins.2017.05.002Open DOISearch in Google Scholar

J.A. Aledo, L.G. Diaz, S. Martinez and J.C. Valverde, Maximum number of periodic orbits in parallel dynamical systems, Inf. Sci. 468 (2018) 63–71. 10.1016/j.ins.2018.08.041.AledoJ.A.DiazL.G.MartinezS.ValverdeJ.C.Maximum number of periodic orbits in parallel dynamical systemsInf. Sci.4682018637110.1016/j.ins.2018.08.041Open DOISearch in Google Scholar

J.A. Aledo, L.G. Diaz, S. Martinez, J.C. Valverde, Predecessors and Garden-of-Eden configurations in parallel dynamical models, J. Comput. Appl. Math. 348 (2019) 26–33. 10.1016/j.cam.2018.08.015.AledoJ.A.DiazL.G.MartinezS.ValverdeJ.C.Predecessors and Garden-of-Eden configurations in parallel dynamical modelsJ. Comput. Appl. Math.3482019263310.1016/j.cam.2018.08.015Open DOISearch in Google Scholar

J.A. Aledo, L.G. Diaz, S. Martinez, J.C. Valverde, Solution to the predecessors and Gardens-of-Eden problems for synchronous systems over directed graphs, Appl. Math. Comput. 370 (2019) 22–28. 10.1016/j.amc.2018.10.077.AledoJ.A.DiazL.G.MartinezS.ValverdeJ.C.Solution to the predecessors and Gardens-of-Eden problems for synchronous systems over directed graphsAppl. Math. Comput.3702019222810.1016/j.amc.2018.10.077Open DOISearch in Google Scholar

J.A. Aledo, L.G. Diaz, S. Martinez, J.C. Valverde, Predecessors existence problems and Garden-of-Eden in sequential dynamical systems, Complexity (in press)AledoJ.A.DiazL.G.MartinezS.ValverdeJ.C.Predecessors existence problems and Garden-of-Eden in sequential dynamical systemsComplexityin pressSearch in Google Scholar

J.A. Aledo, S. Martinez, F.L. Pelayo, J.C. Valverde, Parallel dynamical systems on maxterm and minterm Boolean functions, Math. Comput. Model. 35 (2012), 666–671. 10.1016/j.mcm.2011.08.040.AledoJ.A.MartinezS.PelayoF.L.ValverdeJ.C.Parallel dynamical systems on maxterm and minterm Boolean functionsMath. Comput. Model.35201266667110.1016/j.mcm.2011.08.040Open DOISearch in Google Scholar

J.A. Aledo, S. Martinez, J.C. Valverde, Parallel dynamical systems over directed dependency graphs, Appl. Math. Comput. 219 (2012), 1114–1119. 10.1016/j.amc.2012.07.018.AledoJ.A.MartinezS.ValverdeJ.C.Parallel dynamical systems over directed dependency graphsAppl. Math. Comput.21920121114111910.1016/j.amc.2012.07.018Open DOISearch in Google Scholar

J.A. Aledo, S. Martinez, J.C. Valverde, Parallel discrete dynamical systems on independent local functions, J. Comput. Appl. Math. 237 (2013), 335–339. 10.1016/j.cam.2012.06.002.AledoJ.A.MartinezS.ValverdeJ.C.Parallel discrete dynamical systems on independent local functionsJ. Comput. Appl. Math.237201333533910.1016/j.cam.2012.06.002Open DOISearch in Google Scholar

J.A. Aledo, S. Martinez, J.C. Valverde, Updating method for the computation of orbits in parallel dynamical systems, Int. J. Comput. Math 90 (9) (2013) 1796-1808. 10.1080/00207160.2013.767894.AledoJ.A.MartinezS.ValverdeJ.C.Updating method for the computation of orbits in parallel dynamical systemsInt. J. Comput. Math90920131796180810.1080/00207160.2013.767894Open DOISearch in Google Scholar

J.A. Aledo, S. Martinez and J.C. Valverde. Parallel dynamical systems over graphs and related topics: a survey, J. Appl. Maths 2015 (2015), Article ID 594294, 14 pages. 10.1155/2015/594294.AledoJ.A.MartinezS.ValverdeJ.C.Parallel dynamical systems over graphs and related topics: a surveyJ. Appl. Maths20152015Article ID 5942941410.1155/2015/594294Open DOISearch in Google Scholar

J.A. Aledo, S. Martinez and J.C. Valverde, Graph dynamical systems with general Boolean states, Appl. Math. Inf. Sci. 9 (2015), 1803–1808. 10.12785/amis/090417.AledoJ.A.MartinezS.ValverdeJ.C.Graph dynamical systems with general Boolean statesAppl. Math. Inf. Sci.920151803180810.12785/amis/090417Open DOISearch in Google Scholar

C. Barrett, H. B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, P.T. Tosic, Gardens of Eden and fixed points in sequential dynamical systems, Discrete Math. Theor. Comput. Sci. Proceedings (2001) 95–110.BarrettC.Hunt IIIH. B.MaratheM.V.RaviS.S.RosenkrantzD.J.StearnsR.E.TosicP.T.Gardens of Eden and fixed points in sequential dynamical systemsDiscrete Math. Theor. Comput. Sci. Proceedings200195110Search in Google Scholar

C. Barrett, H. B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, Predecessor and permutation existence problems for sequential dynamical systems, Discrete Math. Theor. Comput. Sci. AB(DMCS) 2003 69-80BarrettC.Hunt IIIH. B.MaratheM.V.RaviS.S.RosenkrantzD.J.StearnsR.E.Predecessor and permutation existence problems for sequential dynamical systemsDiscrete Math. Theor. Comput. Sci. AB(DMCS)20036980Search in Google Scholar

C. Barrett, H. B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, M. Thakur, Predecessor existence problems for finite discrete dynamical systems. Theor. Comput. Sci. 386 (1-2) (2007) 3–37.BarrettC.Hunt IIIH. B.MaratheM.V.RaviS.S.RosenkrantzD.J.StearnsR.E.ThakurM.Predecessor existence problems for finite discrete dynamical systemsTheor. Comput. Sci.3861-22007337Search in Google Scholar

C. Barrett, H. B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, M. Thakur, Errata for the paper “predecessor existence problems for finite discrete dynamical systems” [theoret. comput. sci. 386 (1-2) (2007) 3-37] (10.1016/j.tcs.2007.04.026), Theor. Comput. Sci. 395 (1) (2008) 132–133.BarrettC.Hunt IIIH. B.MaratheM.V.RaviS.S.RosenkrantzD.J.StearnsR.E.ThakurM.Errata for the paper “predecessor existence problems for finite discrete dynamical systems”theoret. comput. sci.3861-2200733710.1016/j.tcs.2007.04.026Theor. Comput. Sci.39512008132133Open DOISearch in Google Scholar

C. Defant, Binary codes and period-2 orbits of sequential dynamical systems, Discrete Math. Theor. Comput. Sci. 19 (3) (2017), Article number 3971.DefantC.Binary codes and period-2 orbits of sequential dynamical systemsDiscrete Math. Theor. Comput. Sci.1932017Article number 3971Search in Google Scholar

W.Y.C. Chen, X. Li, M.J. Zheng, Matrix method for linear sequential dynamical systems on digraphs, Appl. Math. Comput. 160 (1) (2005), 197–212.ChenW.Y.C.LiX.ZhengM.J.Matrix method for linear sequential dynamical systems on digraphsAppl. Math. Comput.16012005197212Search in Google Scholar

C. Defant, Binary codes and period-2 orbits of sequential dynamical systems, Discrete Math. Theor. Comput. Sci. 19 (3) (2017), Article number 3971.DefantC.Binary codes and period-2 orbits of sequential dynamical systemsDiscrete Math. Theor. Comput. Sci.1932017Article number 3971Search in Google Scholar

F. Green, NP-complete problems in cellular automata, Complex systems, 1 (3) (1987) 453–474.GreenF.NP-complete problems in cellular automataComplex systems131987453474Search in Google Scholar

A. Kawachi, M. Ogihara, K. Uchizawa, Generalized predecessor existence problems for boolean finite dynamical systems, Paper presented at the Leibniz International Proceedings in Informatics, LIPIcs (2017) 83.KawachiA.OgiharaM.UchizawaK.Generalized predecessor existence problems for boolean finite dynamical systems, Paper presented at the Leibniz International Proceedings in InformaticsLIPIcs201783Search in Google Scholar

Kawachi, A., Ogihara, M., Uchizawa, K. Generalized predecessor existence problems for boolean finite dynamical systems on directed graphs, Theor. Comput. Sci. (2018) (in press)KawachiA.OgiharaM.UchizawaK.Generalized predecessor existence problems for boolean finite dynamical systems on directed graphsTheor. Comput. Sci.2018in pressSearch in Google Scholar

H.S. Mortveit, C.M. Reidys, Discrete, sequential dynamical systems, Discrete Math. 226 (1-3) (2002) 281–295.MortveitH.S.ReidysC.M.Discrete, sequential dynamical systemsDiscrete Math.2261-32002281295Search in Google Scholar

H.S. Mortveit, C.M. Reidys, An introduction to sequential dynamical systems, Springer, New York, 2007.MortveitH.S.ReidysC.M.An introduction to sequential dynamical systemsSpringerNew York2007Search in Google Scholar

M. Ogihara, K. Uchizawa, Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems. In: Jain R., Jain S., Stephan F. (eds) Theory and Applications of Models of Computation. TAMC 2015. Lecture Notes in Computer Science, vol 9076. Springer, Cham, pp. 87–98.OgiharaM.UchizawaK.Computational Complexity Studies of Synchronous Boolean Finite Dynamical SystemsJainR.JainS.StephanF.Theory and Applications of Models of Computation. TAMC 2015. Lecture Notes in Computer Science9076Springer, Cham8798Search in Google Scholar

M. Ogihara, K. Uchizawa, Computational complexity studies of synchronous boolean finite dynamical systems on directed graphs. Inf. Comput. 256 (2017) 226–236.OgiharaM.UchizawaK.Computational complexity studies of synchronous boolean finite dynamical systems on directed graphsInf. Comput.2562017226236Search in Google Scholar

K. Sutner, On the computational complexity of finite cellular automata, J. Comput. System Sci. 50 (1) (1995) 87–97.SutnerK.On the computational complexity of finite cellular automataJ. Comput. System Sci.50119958797Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo