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

- Sequential dynamical systems
- Boolean functions
- Predecessors
- Garden-of-Eden points

#### MSC 2010

- 90B10
- 37E15
- 94C10
- 94C15
- 05A15

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 (_{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 (_{1}, …, _{n}

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

When the interactions are unidirectional, we can formalize the elements and their relations with a (dependency) directed graph

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

As in [6], for each entity _{D}

that is, the set of all the entities influencing

Also, we consider the sets:

Let _{1}, …, _{n}

a Boolean function such that _{πi}^{n} → {0, 1}^{n} updates the state of the entity _{i}_{D}

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

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

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 _{1}, …, _{n}_{1}, …, _{n}_{1}, …, _{n}_{1}, …, _{n}_{1}, …, _{n}_{1}, …, _{n}

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

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) (_{1}, …, _{n}

Also inspired by the considerations in [7], we will consider the subsets of _{D}_{0}) given by:

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 _{0} (resp. _{0}) is _{0} which is updated, according the order expressed in

For _{1}, similarly, we consider the subsets of _{D}_{1}) given by:

As usually done, we will denote by ^{′} ⊆ ^{′} = ^{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 _{1}, …, _{n}

_{1}, …, _{n}_{1}, …, _{n}

_{1}, …, _{n}_{1}, …, _{n}

To do this proof, we only need to follow similar arguments to those of Theorem 1 in [7], but now using the new subset _{0}, 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 (_{1}, …, _{n}_{1}, …, _{n}_{1}, …, _{n}_{1}, …, _{n}

Secondly, suppose, that (_{1}, …, _{n}_{1}, …, _{n}_{i}_{i}_{0} ∪ _{0}, because any entity in (_{0} ∪ _{0})^{c} ⊆ _{1} updates to the activated state.

If _{0} ∖ _{0} ⊆ _{1}, we have:

Since _{i}_{i}_{r}_{s}_{j}_{j}

_{i}_{i}

∀_{r}_{s}

Since _{i}_{i}_{i}_{0} ∖ _{0}. Thus, we can conclude that _{0}. At this point,

Since _{i}_{r}_{s}_{j}

_{i}_{i}

∀_{r}_{s}_{0}, so _{j}_{j}^{′}.

Since _{i}_{i}_{i}_{0}.

As a consequence, there does not exist _{i}_{i}_{1}, …, _{n}_{1}, …, _{n}

Dually, we have:

_{1}, …, _{n}_{1}, …, _{n}

_{1}, …, _{n}_{1}, …, _{n}

_{1}, …, _{n}_{1}, …, _{n}

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 _{0} (resp. _{1}) involved is different in this context.

_{1}, …, _{n}_{0} ∩ _{0}) ∩ ^{′} ≠ ∅ _{0} ∩ _{1}, …, _{n}

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

_{1}, …, _{n}_{1} ∩ _{1}) ∩ ^{′} ≠ ∅ _{1} ∩ _{1}, …, _{n}

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.

^{n} − 2.

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

if _{i}_{j}_{1}, …, _{n}

if ^{′}, then a state vector with _{i}_{j}_{1}, …, _{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 _{n}_{πn}_{n}_{n}_{n}^{′}. Since the dependency digraph is weekly connected, there exists _{n}_{k}_{πn}

This lower bound is reached in the following example. Let [

MAX =

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

Observe that the condition ^{′} = ∅, or one 2-cycle if

Secondly, we will demonstrate that 2^{n} − 2 is an upper bound for the number of GOE of a MAX-SDDS. Observe that the vector state _{1}, …, _{n}

_{i}

_{i}^{′}.

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

_{i} = 0 if

_{i} = 1 if ^{′},

then _{1} = 0.

Finally, the upper bound is reached in the following example. Let us consider the following [

MAX = _{1} ∨

The phase diagram of this system is:

The following theorems allow us to determine if, given a state (_{1}, …, _{n}_{1}, …, _{n}_{1}, …, _{n}

_{1}, …, _{n}_{1}, …, _{n}

Dually, we can state:

_{1}, …, _{n}_{1}, …, _{n}

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 (_{1}, …, _{n}

_{1}, …, _{n}^{#(V0∪P0)c}.

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

MAX = _{2} ∨ _{3} ∨ ⋯ ∨ _{n}

_{0} = {1}, _{0} = {2}, _{0} = ∅ _{1} = {2, …,

_{1}, …, _{n}_{1} = 1 _{2} = 0, _{1}, …, _{n}

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.

Regarding new wave distributions of the non-linear integro-partial Ito differential and fifth-order integrable equations Nonlinear Mathematical Modelling of Bone Damage and Remodelling Behaviour in Human Femur Value Creation of Real Estate Company Spin-off Property Service Company Listing Entrepreneur's Passion and Entrepreneurial Opportunity Identification: A Moderated Mediation Effect Model Applications of the extended rational sine-cosine and sinh-cosh techniques to some nonlinear complex models arising in mathematical physics Study on the Classification of Forestry Infrastructure from the Perspective of Supply Based on the Classical Quartering Method A Modified Iterative Method for Solving Nonlinear Functional Equation A comprehensive evaluation of county economies in the Beijing-Tianjin-Hebei Region based on entropy TOPSIS analysis New Principles of Non-Linear Integral Inequalities on Time Scales Has the belt and road initiative boosted the resident consumption in cities along the domestic route? – evidence from credit card consumption Analysis of the agglomeration of Chinese manufacturing industries and its effect on economic growth in different regions after entering the new normal Study on the social impact Assessment of Primary Land Development: Empirical Analysis of Public Opinion Survey on New Town Development in Pinggu District of Beijing Possible Relations between Brightest Central Galaxies and Their Host Galaxies Clusters and Groups Attitude control for the rigid spacecraft with the improved extended state observer An empirical investigation of physical literacy-based adolescent health promotion MHD 3-dimensional nanofluid flow induced by a power-law stretching sheet with thermal radiation, heat and mass fluxes The research of power allocation algorithm with lower computational complexity for non-orthogonal multiple access The art design of industrialised manufacturing furniture products based on the simulation of mathematical curves Research on the normalisation method of logging curves: taking XJ Oilfield as an example A Method of Directly Defining the inverse Mapping for a HIV infection of CD4+ T-cells model On the interaction of species capable of explosive growth Research on Evaluation of Intercultural Competence of Civil Aviation College Students Based on Language Operator Combustion stability control of gasoline compression ignition (GCI) under low-load conditions: A review Research on the Psychological Distribution Delay of Artificial Neural Network Based on the Analysis of Differential Equation by Inequality Expansion and Contraction Method The Comprehensive Diagnostic Method Combining Rough Sets and Evidence Theory Study on Establishment and Improvement Strategy of Aviation Equipment Design of software-defined network experimental teaching scheme based on virtualised Environment Research on Financial Risk Early Warning of Listed Companies Based on Stochastic Effect Mode System dynamics model of output of ball mill The Model of Sugar Metabolism and Exercise Energy Expenditure Based on Fractional Linear Regression Equation Constructing Artistic Surface Modeling Design Based on Nonlinear Over-limit Interpolation Equation Statistical analysis of typical elevator accidents in China from 2002 to 2019 Optimal allocation of microgrid using a differential multi-agent multi-objective evolution algorithm About one method of calculation in the arbitrary curvilinear basis of the Laplace operator and curl from the vector function Numerical Simulation Analysis Mathematics of Fluid Mechanics for Semiconductor Circuit Breaker Cartesian space robot manipulator clamping movement in ROS simulation and experiment Effects of internal/external EGR and combustion phase on gasoline compression ignition at low-load condition Research of urban waterfront space planning and design based on children-friendly idea Characteristics of Mathematical Statistics Model of Student Emotion in College Physical Education Human Body Movement Coupling Model in Physical Education Class in the Educational Mathematical Equation of Reasonable Exercise Course Sensitivity Analysis of the Waterproof Performance of Elastic Rubber Gasket in Shield Tunnel Impact of Web Page House Listing Cues on Internet Rental Research on management and control strategy of E-bikes based on attribute reduction method A study of aerial courtyard of super high-rise building based on optimisation of space structure Exact solutions of (2 + 1)-Ablowitz-Kaup-Newell-Segur equation