UPDATE SCHEDULES OF SEQUENTIAL DYNAMICAL SYSTEMS

REINHARD LAUBENBACHER AND BODO PAREIGIS

Abstract. Sequential dynamical systems have the property, that the updates of states of individual cells occur sequentially, so that the global update of the system depends on the order of the individual updates. This order is given by an order on the set of vertices of the dependency graph. It turns out that only a partial suborder is necessary to describe the global update. This paper defines and studies this partial order and its influence on the global update function.

Introduction

The theory of sequential dynamical systems (SDS) was first introduced in [1, 2, 3], with the goal of providing a mathematical foundation for computer simulations. Such a foundation will allow a rigorous mathematical analysis of a variety of questions that arise in simulation practice. Many computer simulations can be represented in terms of sequential dynamical systems for computational purposes. By design SDS carry more internal structure than, say, cellular automata. As a result it is possible to prove general results about SDS relating their structural properties to the dynamics they generate. This represents an important first step toward an understanding of how local properties of a system affect global dynamics.

In [6] we generalized the notion of a sequential dynamical system, and defined transformations of SDS. Such transformations are compatible with the internal structure and induce a transformation of the associated state spaces, that is, are compatible with the dynamics generated by the systems. One important role such transformations can play is as mathematical formalizations of a simulation of one SDS by another. Such important practical questions as how to reduce the dimension of a simulation can be phrased in this way. Transformations also allow the study of the relationship between structural changes in a simulation to the resulting changes in the dynamics.

A second role for transformations is in a structure theory of SDS as the first step toward a classification. For instance, in [6] it was shown that every SDS can be uniquely decomposed into a product of indecomposable SDS, which can then be studied individually.

Finally, a third role is in comparing SDS with other interesting objects in computer science used for simulations and as computational devices. This can be done very well in a categorical framework, and one goal of this research is to develop a good categorical setting for the study of SDS.

1Keywords: sequential dynamical system, morphism of pographs, poset models of graphs, update schedules.

Date: February 19, 2003.

2000 Mathematics Subject Classification. Primary: 37B99, 68Q65, 93A30; Secondary: 18B20, 37B19, 68R01.

Recall from [6] that a sequential dynamical system is a function

f : ∏_{i=1}^{n} k_{i} ⟶ ∏_{i=1}^{n} k_{i},

on strings of length n, with entries in the ith component coming from a specified set k_{i}. We simply write k^{n} := ∏_{i=1}^{n} k_{i}. This function f : k^{n} ⟶ k^{n} is obtained from the following data:

(1) a dependency graph F on n vertices;

(2) a collection of local update functions f_{i} : k^{n} ⟶ k^{n}, i = 1, …, n, which change only the ith coordinate, and whose inputs are controlled by the graph F,

(3) an update schedule α, consisting of a word in n letters a_{1}, …, a_{n} from the set of vertices V_{F} of F.

The function f is the composition of the f_{i}, in the order specified by the update schedule α. (More details can be found in the next section.)

It was shown in [4] that the graph F is implicit in the rest of the data, using a Galois correspondence between collections of local functions and graphs, constructed in [5]. Thus, if expedient, this part of the structure of an SDS may be ignored.

The focus in the present paper is on the update schedule α. Recall that the global update function of the SDS is generated by composing the local update functions in the order prescribed by α. Part of the work reported in [2, 3] concerned the extent to which changes in the update schedule affect the global update function, respectively, the resulting dynamic structure. (In contrast to [6] and the present paper the update schedule in [2, 3] is taken to be a permutation of the indices of the nodes, rather than a general finite word in a subset of those indices.) It was shown that some changes in the update schedule leave the global update function unchanged. This is similar to a distributed computation in which certain steps can be carried out in various orders, whereas others need to be done according to a prescribed schedule so that the end result remains unchanged. We want to find properties of an update schedule on which the global update function depends and other properties that can freely be changed without changing the global update function and thus the dynamic behavior of the whole system.

We show in this paper that this degree of freedom in the update schedule is a very important aspect of an SDS that deserves to be studied as part of the explicit structure of the SDS. This leads us to propose a new definition of SDS which incorporates this dichotomy of the update schedule. We will see in a subsequent paper that such a change leads to a notion of transformations of SDS with very desirable properties. In particular, we obtain a categorical framework for SDS that is rich in transformations and structure.

In order to describe and study the ordering of the vertices given by the update schedule we introduce the notion of a poset model of a graph, an interesting connection between posets and graphs. Let F be a finite graph (e.g., the dependency graph of an SDS), and let

α : {1, …, n} ⟶ V_{F}

be an update schedule, i.e. a function into the set of vertices of F. Any update schedule a_{1}, …, a_{n} of an SDS can be represented as such a function. The key result of this paper is that there exists a unique poset O_{F} and poset model β : O_{F} ⟶ V_{F} of the graph F together with a function γ : O_{F} ⟶ {1, …, n}, i.e.

{1, …, n} ⟵^{γ} O_{F} ⟶^{β} V_{F} ,

where γ is invertible and order preserving, such that α = γ^{−1} ∘β. That is, we can decompose the update schedule α into a poset model β of the graph F (called pograph) and an update schedule γ for the pograph β : O_{F} ⟶ V_{F}.

Surprisingly, it turns out that the pograph β : O_{F} ⟶ V_{F} completely determines the dynamical behavior of the SDS. Consequently, we can define SDS on a pograph O_{F} ⟶ V_{F} alone instead of on a graph F together with an update schedule α.

It will turn out that the definition of morphisms of SDS defined on pographs becomes very natural and straightforward.

If the map β is bijective, and we view the poset O_{F} as a directed graph via its Hasse diagram, then β becomes a graph map which induces an acyclic orientation on F. In [7, Prop. 1] it is shown that there is a one-to-one correspondence between acyclic orientations on a graph F on n vertices and the set of equivalence classes of permutations on n letters for a certain equivalence relation. The equivalence relation is generated by making two permutations equivalent if they differ by transpositions of adjacent elements whose corresponding vertices are not connected by an edge in F. The SDS defined by Barrett et. al., called permutation SDS in [6], use an update schedule given by a permutation, that is, every local update function is used exactly once in the composition that defines the global update function of the SDS. It was shown in [3] that from an acyclic orientation of F one can construct different update schedules α, which all produce the same global update function. That is, an acyclic orientation of F contains enough information to construct the global update function. This result was used in [3] to derive a sharp upper bound on the number of different global update functions that can be generated by varying the update schedule, for a fixed graph F and fixed local update functions.

In the more general setting considered here, the pograph β : O_{F} ⟶ V_{F} is taking the place of the acyclic orientation of F. We will show that for a fixed β it does not matter what choice we make for the corresponding γ in order to study the dynamic behavior. The global update function is independent of the choice of γ. As a corollary we obtain a one-to-one correspondence between pographs with m elements on a graph F and equivalence classes of update schedules {1, …, m} ⟶ V_{F}. The equivalence relation is generated by setting two update schedules α and α′ equivalent if they generate the same global update function f_{α} = f_{α′} from any family of local update functions f_{α(i)}.

1. Sequential dynamical systems and graphs with update schedule.

For the convenience of the reader we repeat the definition of sequential dynamical systems as used in [6]. We will rephrase that definition under some new points of view. Some of the basic notions are explained in the following Remark 1.1. Let X be a set and let P(X) be its power set. Let P_{2}(X) ⊆ P(X) be the subset of all two-element subsets of X.

A (loop free, undirected) graph F = (V_{F} , E_{F}) consists of a set V_{F} of vertices and a subset E_{F} ⊆ P_{2}(V_{F}) of edges.

Let F be a graph. A 1-neighborhood N(a) of a vertex a ∈ V_{F} is the set

N(a) := {b ∈ V_{F} |{a, b} ∈ E_{F} or a = b}.

Let Z be a subcategory of the category of sets. Let (k[a]|a ∈ V_{F}) be a family of sets in Z, e.g. finite sets. The set k[a] will be called the set of local states at a. Define

k^{V_{F}} := ∏_{a∈V_{F}} k[a],

the set of (global) states of F. In case V_{F} is finite with r elements we write

k^{r} := k[a_{1}] × … × k[a_{r}].

We use the following notation. For a state x ∈ k^{r} and a vertex a ∈ V_{F} we write x[a] for the state of the vertex a or the a-th component of x so that

x = (x[a]|a ∈ V_{F}) or x = (x[a_{1}], …, x[a_{r}]).

In case that all k[a] are equal to a set k, this definition reduces to the usual definition of k^{V_{F}} resp. k^{r}.

A function f : k^{V_{F}} ⟶ k^{V_{F}} is called local at a_{i} ∈ V_{F} if

f(x)[a_{j}] = \begin{cases}x[a_{j}], & if a_{j} ≠ a_{i}, \\ f^{i}(x), & if a_{j} = a_{i}. \end{cases}

where f^{i}(x) = f^{i}((x[a]|a ∈ V_{F})) ∈ k[a_{i}] depends only on the states x[a] of those variables a that are in the 1-neighborhood N(a_{i}) of the vertex a_{i}.

If V_{F} is finite this means the following. A function f : k^{r} ⟶ k^{r} is local at a_{i} ∈ V_{F} if

f(x[a_{1}], …, x[a_{r}]) = (x[a_{1}], …, x[a_{i−1}], f^{i}(x[a_{1}], …, x[a_{r}]), x[a_{i+1}], …, x[a_{r}]),

where f^{i}(x[a_{1}], …, x[a_{r}]) ∈ k[a_{i}] depends only on the states x[a_{j}] of those vertices a_{j} that are in the 1-neighborhood N(a_{i}) of the vertex a_{i}.

One of the fundamental observations is the following easy fact. If a, b ∈ V_{F} such that {a, b} ∉ E_{F} then f_{a} ∘ f_{b} = f_{b} ∘ f_{a} if f_{a} and f_{b} are local functions. Definition 1.2. Let F be a graph. A map α : {1, …, n} ⟶ V_{F} is called an update schedule of length n for F. A pair (F, α) is called a graph with update schedule or a ugraph F. Definition 1.3. A sequential dynamical system (SDS) ^{1} on a ugraph F

F = (F, (k[a]|a ∈ V_{F}), (f_{a}|a ∈ V_{F}))

consists of

(1) a finite ugraph F,

(2) a family of sets (k[a]|a ∈ V_{F}) in Z,

(3) a family of local functions (f_{a} : k^{r} ⟶ k^{r}|a ∈ V_{F} , f_{a} local at a) in Z. Remark 1.4. The update schedule α : {1, …, n} ⟶ V_{F} of a ugraph F of an SDS F defines an associated global update function of the SDS F

f_{α} := f_{α(1)} ∘ … ∘ f_{α(n)} : k^{r} ⟶ k^{r}.

1Subsequently, we will use the acronym SDS for plural as well as singular instances.

For the moment we consider an update schedule just as an additional structure of the graph used in the definition of an SDS. We will call the graph F with this (or possibly another) additional structure on which an SDS is defined the basis of the given SDS. Surprisingly a map α : {1, …, n} ⟶ V_{F} induces an interesting additional structure on the graph F that we will subsequently study.

2. Poset models of graphs

In this section we show the relationship between a graph with update schedule and an associated partially ordered set together with a certain map into the graph which we call a poset model of F.

Let O be a poset (partially ordered set) with order relation ≤. We define

i ◁ j : ⟺ (i < j and ∀k ∈ O : i ≤ k ≤ j ⟹ i = k or k = j),

i.e., j is an immediate successor of i. Theorem 2.1. Let F be a ugraph with update schedule α : {1, …, n} ⟶ V_{F}. Then there are maps

{1, …, n} ⟵^{γ} O_{F} ⟶^{β} V_{F}

with

• a finite poset O_{F},

• a bijective order preserving map γ : O_{F} ⟶ {1, …, n} and • a map β : O_{F} ⟶ V_{F}

such that

(1) ∀i, j ∈ O_{F} : i ◁ j ⟹ {β(i), β(j)} ∈ E_{F},

(2) ∀i, j ∈ O_{F} : {β(i), β(j)} ∈ E_{F} ⟹ i ≤ j ∨ j ≤ i,

(3) α = βγ^{−1}.

Proof. The poset O_{F} is constructed as follows. Define O_{F} := {1, …, n} with the following partial order. Define

i ˙≺ j : ⟺ (i ≤ j ∧ {α(i), α(j)} ∈ E_{F}).

Let i ⪯ j be the reflexive and transitive closure of the relation ˙≺.

Then (O_{F} , ⪯) is a poset since i ⪯ j and j ⪯ i implies that there are chains i = i_{1} ˙≺ i_{2} ˙≺ … ˙≺ i_{r} = j and j = j_{1} ˙≺ j_{2} ˙≺ … ˙≺ j_{s} = i. From this we get i = i_{1} ≤ i_{2} ≤ … ≤ i_{r} = j and j = j_{1} ≤ j_{2} ≤ … ≤ j_{s} = i hence i = j.

Furthermore β := α : O_{F} = {1, …, n} ⟶ V_{F} satisfies (1), for let i◁j then j is an immediate successor of i in (O_{F} , ⪯), so we must have i ˙≺ j since these pairs generate the order on O_{F}. But that implies {β(i), β(j)} ∈ E_{F}. Assume now that {β(i), β(j)} ∈ E_{F} holds. Since i ≤ j or j ≤ i in {1, …, n} we get i ˙≺ j or j ˙≺ i hence i ⪯ j or j ⪯ i. So (2) is satisfied.

By construction γ := id : O_{F} ⟶ {1, …, n} is bijective. It is order preserving since i ⪯ j implies that there is a chain i = i_{1} ˙≺ i_{2} ˙≺ … ˙≺ i_{r} = j. From this we get i = i_{1} ≤ i_{2} ≤ … ≤ i_{r} = j.

Obviously α = βγ^{−1}. □

Observe that i ◁ j in O_{F} implies i ˙≺ j, but the converse does not hold in general. Definition 2.2. Let F be a graph and O_{F} be a poset. Let β : O_{F} ⟶ V_{F} be a map satisfying ∀i, j ∈ O_{F}:

(1) i ◁ j ⟹ {β(i), β(j)} ∈ E_{F},

(2) {β(i), β(j)} ∈ E_{F} ⟹ i ≤ j ∨ j ≤ i

Then β : O_{F} ⟶ V_{F} is called a poset model of the graph F or a pograph. Remark 2.3. Theorem 2.1 says that we can construct a pograph (F, O_{F} , β) together with a bijective order preserving map γ : O_{F} ⟶ {1, …, n} from a ugraph (F, α). Conversely if we have a pograph (F, O_{F} , β) together with a bijective order preserving map γ : O_{F} ⟶ {1, …, n} then we get a ugraph with update schedule α := βγ^{−1}.

If β in the definition of a pograph is bijective then this is the same as an acyclic orientation of the graph F as discussed in [7]. In this case the map β and the order of the poset O_{F} defines an orientation on each edge of F by condition (2). Since O_{F} is a poset the orientation on all of F (as it is defined) will be acyclic, i.e. there are no cycles. Condition (1) means that the order of O_{F} is “generated” by the graph. If α is injective then some of the edges will be oriented, the orientation of the edges will be transitive, and F with this orientation will be acyclic . Else it may happen that edges are oriented in both directions. Example 2.4. An example is α : {1, 2, 3, 4} ⟶ {a, b, c} = V_{F} where all vertices are connected by an edge and α(1) = α(4) = a, α(2) = b, α(3) = c. Then 1 ˙≺ 2 ˙≺ 3 ˙≺ 4, 1 ˙≺ 3, and 2 ˙≺ 4, and the edges {a, b} and {a, c} are directed in both directions. Furthermore O_{F} = {1, 2, 3, 4} as posets, in particular 1 ⪯ 4 but 1 ˙≺ 4 does not hold. Definition 2.5. Let (F, O_{F} , β) be a pograph. A bijective, order preserving map γ : O_{F} ⟶ {1, …, n} is called an update schedule for (F, O_{F} , β). The pair ((F, O_{F} , β), γ) is called a pograph with update schedule.

Now Theorem 2.1 says that we can construct a pograph with update schedule out of every ugraph. Conversely we can construct a ugraph out of every pograph with update schedule in the obvious way. These two constructions are almost inverses of each other. Proposition 2.6. Let F = (F, O_{F} , β, γ) and (F, O′_{F} , β′, γ′) be finite pographs with update schedules γ : O_{F} ⟶ {1, …, n} and γ′ : O′_{F} ⟶ {1, …, n} resp. Assume that βγ^{−1} = β′γ′^{−1}. Then there is a unique isomorphism of posets δ : O_{F} ⟶ O′_{F} such that γ = γ′δ and β = β′δ.

Proof. Obviously δ := γ′^{−1}γ is the only choice for this map and δ satisfies γ = γ′δ and β = β′δ. We only have to show that δ is order preserving, since the inverse map will also be order preserving by the symmetry of the situation. Let i, j ∈ O_{F}. Since O_{F} is finite we only have to show

i ◁ j ⟹ δ(i) ≤ δ(j).

Since i ◁ j implies {β(i), β(j)} ∈ E_{F} we get {β′δ(i), β′δ(j)} ∈ E_{F} hence δ(i) ≤ δ(j) ∨ δ(j) ≤ δ(i). Assume that δ(j) ≤ δ(i) holds. Then we have γ(j) = γ′δ(j) ≤ γ′δ(i) = γ(i), a contradiction to i ◁ j. Thus δ(i) ≤ δ(j). □

So we see that the pograph with update schedule (F, O_{F} , β, γ) constructed from a ugraph (F, α) by Theorem 2.1 is unique up to an isomorphism (of posets), compatible with the update schedule and with the pograph map β.

Definition 2.7. Let (F, O_{F} , β, γ) and (F, O′_{F} , β′, γ′) be finite pographs with update schedule. A strong isomorphism between these pographs with update schedule is an isomorphism of posets δ : O_{F} ⟶ O′_{F} such that γ = γ′δ and β = β′δ.

Observe that for a strong isomorphism we have βγ^{−1} = β′δγ^{−1} = β′γ′^{−1}. Obviously strong isomorphisms define an equivalence relation and the above observations give Corollary 2.8. The constructions given in Theorem 2.1 and Proposition 2.6 define a bijection between ugraphs and strong isomorphism classes of pographs with update schedules.

The next proposition relates the notion of pograph with update schedule to the permutation update schedules used by Barrett et. al. . For a given graph F on n vertices {1, …, n} define an equivalence relation ∼_{F} on the permutations in S_{n} as follows. Let π, π′ ∈ S_{n}, denoted by π = (i_{1}, …, i_{n}) and π′ = (i′_{1}, …, i′_{n}). (That is, π(j) = i_{j}, etc.) Then π ∼_{Y} π′ if there is a k ∈ {1, …, n} such that i_{j} = i′_{j} for all j ≠ k, k + 1 and there is no edge in F connecting vertices i_{k} and i_{k+1}. Let ∼_{F} be the equivalence relation generated by this relation. Denote by S_{n}/ ∼_{F} the set of equivalence classes. Let A_{F} denote the set of acyclic orientations on F. Proposition 2.9. [7, Prop. 1] There is a one-to-one correspondence between A_{F} and S_{n}/ ∼_{Y}.

The next result shows how the new concepts of poset model and pograph with update schedule reduce to the case of permutation update schedules used in permutation SDS. Let I_{F} denote the set of strong isomorphism classes of bijective pographs with update schedule on F (that is, β is bijective). Proposition 2.10. There is a one-to-one correspondence between I_{F} and A_{F}, hence a oneto-one correspondence between the set of strong isomorphism classes of bijective poset models and S_{n}/ ∼_{Y}.

Proof. Let β : O_{F} ⟶ F be a poset model of F, and assume that β is bijective. We define an acyclic orientation O of F as follows. Let {u, v} be an edge of F. Then u = β(i) and v = β(j) for some i, j ∈ O_{F}. Since β is a poset model, we have that i ≤ j or j ≤ i. If i ≤ j, then orient the edge (u, v) from u to v. Since β is onto, every edge of F is oriented in this way. It is straightforward to see that this orientation is acyclic, since O_{F} is a partial order.

If β′ : O′_{F} ⟶ F is another poset model of F which is strongly isomorphic to β via an isomorphism φ : O_{F} ⟶ O′_{F}, then it is clear that β′ induces the same orientation on F.

Conversely, let O be an acyclic orientation of F. Then O defines a partial order on the vertices of F, by setting u < v if there is an oriented path in O from u to v. Then id : O ⟶ F is a poset model of F. Together with Prop. 1 in [7] this completes the proof of the first statement. □

As outlined in the introduction, from the point of view of the global update function of an SDS, there is a certain amount of freedom on the order prescribed by an update schedule. There are those order relations that need to be kept fixed if the global update function is not to be changed, and then there are order relations that can be reversed without affecting the global update function. The previous proposition shows that these two aspects of an update schedule are neatly separated in a pograph with update schedule, the poset model β which encodes those order relations that are required, and the update schedule γ which contains all choices that are available in the update schedule that do not affect the global update function.

3. Morphisms of pographs and of ugraphs

In this section we define morphisms of ugraphs and of pographs with update schedules. The two resulting categories are equivalent. This result will form the basis for a shift from considering SDS on ugraphs to SDS on pographs. The definition of morphisms of pographs is very natural, and, as a consequence, the definition of morphisms of SDS on pographs will be very natural as well.

Definition 3.1. Let F = (F, O_{F} , β_{F}) and G = (G, O_{G}, β_{G}) be two pographs. A morphism of pographs φ : F ⟶ G is a pair of morphisms (φ_{g}, φ̃) where

φ_{g} : F ⟶ G is a morphism of graphs and φ̃: O_{F} ⟶ O_{G} is a morphism of posets

such that the diagram

[figure: φ̃; φ_{g}; O_{F}; V_{F}; β_{F}; O_{G}; V_{G}; β_{G}]

commutes.

The composition of morphisms of pographs is again a morphism of pographs. So we obtain a category Pograph of pographs.

Next we define morphisms of ugraphs. The following discussion will compare our new definition of a morphism of pographs with the definition we used in the discussion of SDS in [6]. Let (F, α : {1, …, m} ⟶ V_{F}) be a ugraph. For each connected component F_{(l)} of F let |α_{(l)}| ⊆ {1, …, m} denote the preimage of F_{(l)} under the map α. Consider |α_{(l)}| as an ordered set, the order being induced by the natural order of {1, …, m}. We also define |α| := ˙⋃|α_{(l)}| with the order induced by the components |α_{(l)}|. Then the identity map id : |α| ⟶ {1, …, n} is a morphism of posets, but not an isomorphism, since certain pairs may be unordered in |α| whereas all pairs are ordered in {1, …, n}. We say that |α| has a coarser partial order than {1, …, n}.

Observe that |α| is a disjoint union of totally ordered sets, one for each connected component of F, which is equal to {1, …, n} if F is connected.

Definition 3.2. Let (F, α_{F} : {1, …, m} ⟶ V_{F}) and (G, α_{G} : {1, …, n} ⟶ V_{G}) be ugraphs. A morphism of ugraphs φ : F ⟶ G consists of

- a morphism of graphs φ_{g} : F ⟶ G and - a morphism of posets φ̃: |α_{F} | ⟶ |α_{G}| such that

[figure: |α_{F} |; V_{F}; α_{F}; |α_{G}|; V_{G}; α_{G}; φ̃; φ_{g}]

commutes. Ugraphs together with these morphisms form a category Ugraph.

This definition is equivalent to what we used in [6]. There we studied a pairs (φ_{g}, (φ̃_{(l)})) satisfying the condition:

(∗)

- φ_{g} : F ⟶ G is a graph morphism,

- the family

φ̃_{(l)} : |(α_{F})_{(l)}| ⟶ {1, …, n}

for each connected component F_{(l)} of F is a family of order preserving maps,

- ∀l ∀j ∈ |(α_{F})_{(l)}| : φ_{g}(α_{F} (j)) = α_{G}(φ̃_{(l)}(j)), i.e. all φ̃_{(l)} are compatible with the given graph morphism φ_{g}.

Indeed we have

Proposition 3.3. Let (F, α_{F} : {1, …, m} ⟶ V_{F}) and (G, α_{G} : {1, …, n} ⟶ V_{G}) be ugraphs.

(1) Let (φ_{g}, (φ̃_{(l)})) satisfy condition (∗). Then φ̃ : |α_{F} | ⟶ |α_{G}| with φ̃(i) := φ̃_{(l)}(i) for all i ∈ |(α_{F})_{(l)}| is a morphism of posets and φ = (φ_{g}, φ̃) is a morphism of ugraphs.

(2) Conversely let φ = (φ_{g}, φ̃) be a morphism of ugraphs. Then φ_{g} together with the family of maps

φ̃_{(l)} : |(α_{F})_{(l)}| ⊆ |α_{F} | \underrightarrow{φ̃} |α_{G}| ⟶^{id} \{1, …, n\}

satisfy condition (∗).

Proof. (1) Since |α_{G}| has a coarser order than {1, …, n} we have to show that φ̃ : |α_{F} | ⟶ |α_{G}| is order preserving. Let i, j ∈ |α_{F} | be given with i ≤ j. Then by definition of the partial order on |α_{F} | there is a unique connected component F_{(l)} with α_{F} (i), α_{F} (j) ∈ F_{(l)} so that i, j ∈ |(α_{F})_{(l)}|. Thus φ̃_{(l)}(i) ≤ φ̃_{(l)}(j) and hence φ̃(i) ≤ φ̃(j) in {1, …, n}. Since φ_{g}(F_{(l)}) ⊆ G_{(l′)} for a unique connected component of G we get φ̃(i), φ̃(j) in |(α_{G})_{(l′)}| hence φ̃(i) ≤ φ̃(j) in |(α_{G})_{(l′)}| and also in |α_{G}|. By the compatibility of φ̃_{(l)} with φ_{g} we get the commutativity of the square.

(2) Obviously φ̃_{(l)} is order preserving and satisfies the compatibility condition of φ̃_{(l)} with φ_{g}. □

The definition of morphisms of pographs and of ugraphs are very similar. A ugraph, however, contains the complete information on an update schedule, whereas a pograph contains only part of this information. The main point is that O_{F} and |α_{F} | are different posets!

Lemma 3.4. Let F = (F, α_{F} : {1, …, m} ⟶ V_{F}) and G = (G, α_{G} : {1, …, n} ⟶ V_{G}) be ugraphs and let φ : F ⟶ G with φ = (φ_{g}, φ̃) be a morphism of ugraphs. Let (F, O_{F} , β_{F} : O_{F} ⟶ V_{F} , γ_{F} : O_{F} ⟶ {1, …, m}) and (G, O_{G}, β_{G} : O_{G} ⟶ V_{G}, γ_{G} : O_{G} ⟶ {1, …, n}) resp. be the pographs with update schedule as constructed in Theorem 2.1. Then φ induces a morphism of pographs such that

[figure: {1, …, m}; |α_{F} |; id; O_{F}; γ_{F}; V_{F}; β_{F}; {1, …, n}; |α_{G}|; id; O_{G}; γ_{G}; V_{G}; β_{G}; φ̃; φ̃; φ_{g}]

commutes.

Proof. Since the underlying sets of O_{F} and of |α_{F} | are equal to {1, …, m} and the map γ_{F} is the identity, the left square commutes. The same set theoretic argument shows that the right square commutes. We have to show that γ_{F} and φ̃: O_{F} ⟶ O_{G} are order preserving.

Let i, j ∈ O_{F} with i ˙≺ j be given. Then i ≤ j in {1, …, m} and {β_{F} (i), β_{F} (j)} ∈ E_{F}. Thus β_{F} (i) and β_{F} (j) are contained in a common connected component F_{(l)} of F and hence i ≤ j in |α_{F} |. This shows that γ_{F} is order preserving.

Furthermore φ̃(i) ≤ φ̃(j) in |α_{G}| and in {1, …, n}. Since {β_{G}φ̃(i), β_{G}φ̃(j)} ∈ E_{G} we get φ̃(i) ˙≺φ̃(j) in O_{G}. So φ̃: O_{F} ⟶ O_{G} is also order preserving. □

We have now proved the following Theorem 3.5. The constructions given in Theorem 2.1 and Lemma 3.4 define a embedding functor

Q : Ugraph ⟶ Pograph

by

Q((F, α_{F} : {1, …, n} ⟶ V_{F})) = (F, O_{F} , β_{F} : O_{F} ⟶ V_{F})
Q((φ_{g}, φ̃: |α_{F} | ⟶ |α_{G}|)) = (φ_{g}, φ̃: O_{F} ⟶ O_{G}).

Remark 3.6. From the point of view of SDS, pographs and their morphisms are useless since in the course of the construction of the global update function we need the full total order on the poset. Recall that the local update functions are composed in this total order to give the global update function. However, we will show that we always may complete the partial order of O to a linear order.

Now two questions arise in this context. First, is the construction of the global update function independent of the choice of this total completion of the order? And second, can the completion of the order be chosen in such a way, that it is compatible with morphisms of pographs, so that the construction of the global update function defines a functor? In the end both questions will be answered to the affirmative.

In the following example we will show the following. Given two ugraphs (F, α_{F}) and (G, α_{G}) there may be a morphism from the associated pograph (F, O_{F} , β_{F}) to (G, O_{G}, β_{G}) that does not arise from a morphism of ugraphs (φ_{g}, φ̃) : (F, α_{F}) ⟶ (G, α_{G}). This shows that the functor Q : Ugraph ⟶ Pograph is not full. This is almost a counterexample to the second question. The example seems to show that there can be morphisms of pographs that do not arise from morphisms of ugraphs. Compare, however, Theorem 3.15. Example 3.7. We define two ugraphs. Let F = G with V_{F} = {a, b, c} and E_{F} = {{a, b}, {a, c}}. Let α_{F} : {1, 2, 3} ⟶ V_{F} be given by α_{F} (1) = a, α_{F} (2) = b, α_{F} (3) = c. Let α_{G} : {1, 2, 3} ⟶ V_{G} be given by α_{G}(1) = a, α_{G}(2) = c, α_{G}(3) = b.

Then O_{F} = O_{G} = {1, 2, 3} with 1 ⪯ 2 and 1 ⪯ 3. Furthermore β_{F} (1) = a = β_{G}(1), β_{F} (2) = b = β_{G}(3), β_{F} (3) = c = β_{G}(2).

Hence (φ_{g}, φ̃) : (F, O_{F} , β_{F}) ⟶ (G, O_{G}, β_{G}) with φ_{g} = id and φ̃(1) = 1, φ̃(2) = 3, φ̃(3) = 2 is a morphism of pographs.

Since both graphs have only one connected component we have |α_{F} | = {1, 2, 3} = |α_{G}| with the natural total order. Hence φ̃: |α_{F} | ⟶ |α_{G}| as defined above is not order preserving.

So the morphism (φ_{g}, φ̃) : (F, O_{F} , β_{F}) ⟶ (G, O_{G}, β_{G}) of pographs is not induced by any morphism of ugraphs from (F, α_{F}) to (G, α_{G}).

If a pograph (F, O_{F} , β_{F}) has an update schedule γ : O_{F} ⟶ V_{F} then (F, O_{F} , β_{F}) ≅ Q((F, β_{F} γ_{F}^{−1})). So different ugraphs can have isomorphic images under Q. They clearly differ only in their update schedules. The question if Q is a representative functor, i.e. if for every object Y ∈ Pograph there is an X ∈ Ugraph with Q(X) ≅ Y, is answered in the following.

We use the following proposition about ordered sets. Proposition 3.8. Let (O, ≤) be a poset and (T , ≤) be a totally ordered set. Let φ : (O, ≤) ⟶ (T , ≤) be a poset map. Then there is a total order ≤′ on O extending ≤ such that φ : (O, ≤′) ⟶ (T , ≤) is a poset map.

Proof. We consider the set of pairs (U, ≤_{U}) with U ⊆ O and ≤_{U} a total order on U, that is an extension of ≤ |_{U}, the order ≤ on O restricted to U, such that φ|_{U} : (U, ≤_{U}) ⟶ (T , ≤) is a poset map. The set S of these pairs is inductively ordered by (U, ≤_{U}) ⊑ (V, ≤_{V}) iff U ⊆ V and (≤_{V})|_{U} =≤_{U}. Thus S has a maximal element (U, ≤′) by Zorn’s Lemma.

Assume U ≠ O. Let x ∈ O \ U. Define U_{x} := {u ∈ U|φ(u) < φ(x) or ∃w ∈ U : u ≤′ w ≤ x}. Define the following relation ≤′′ on U ∪ {x} where u, v ∈ U

u ≤′′ v ⟺ u ≤′ v;
u ≤′′ x ⟺ u ∈ U_{x};
x ≤′′ v ⟺ v ∉ U_{x};
x ≤′′ x.

It is easy to show that this is an element in S. Reflexivity and symmetry of ≤′′ are clear from the definition. Furthermore it is clear by definition that this is a total order as soon as we have proved transitivity. The only important cases for transitivity are u ≤′′ x ∧ x ≤′′ v, x ≤′′ u ≤′′ v, and u ≤′′ v ≤′′ x. These are easy exercises in the axioms for the new order. So is the fact that ≤′′ extends ≤.

Then it is clear that ≤′′ is a continuation of ≤′. This is a contradiction to the maximality of (U, ≤′). Hence U = O. □

Corollary 3.9. [8] Let (O, ≤) be a poset. Then there is a total order ≤′ on O extending ≤.

Proof. In the theorem take T as the one-element totally ordered set and φ the only possible map. □

Observe that the proof of Proposition 3.8 is non-constructive, but that it has sufficient constructive ingredients, in particular the construction of U ∪ {x} and its order, to define an algorithm in case the sets of interest (e.g. SDS) are finite.

Now we return to the discussion of pographs. Corollary 3.10. Let (F, O, β) be a pograph. Then there exists an update schedule γ : O ⟶ {1, …, n}. Corollary 3.11. The embedding functor

Q : Ugraph ⟶ Pograph

is a representative functor. Definition 3.12. Let (F, γ_{F} : O_{F} ⟶ {1, …, m}) and (G, γ_{G} : O_{G} ⟶ {1, …, n}) be pographs with update schedules. A morphism of pographs with update schedule consists of

- a morphism of graphs φ_{g} : F ⟶ G,

- a morphism of posets φ̃: O_{F} ⟶ O_{G}

such that

(1) the diagram

[figure: O_{F}; V_{F}; β_{F}; O_{G}; V_{G}; β_{G}; φ̃; φ_{g}]

commutes and

(2) for all i, j ∈ O_{F} with β_{F} (i) and β_{F} (j) contained in a common connected component

of F

γ_{F} (i) ≤ γ_{F} (j) ⟹ γ_{G}φ̃(i) ≤ γ_{G}φ̃(j).

Remark 3.13. It is clear that the composition of two morphisms of pographs with update schedule is again a morphism of pographs with update schedule. Thus pographs with update schedule (F, γ_{F}) as objects and their morphisms form a category Upograph. Theorem 3.14. There is an equivalence between the category of ugraphs and the category of pographs with update schedule

P : Ugraph ≃ Upograph.

Proof. The construction given in Theorem 2.1 defines an pograph with update schedule P((F, α_{F})) = (F, O_{F} , β_{F} , γ_{F}) for every ugraph (F, α_{F}). Conversely every pograph (F, O_{F} , β_{F}) with update schedule γ_{F} : O_{F} ⟶ {1, …, n} defines a ugraph P′((F, O_{F} , β_{F} , γ_{F})) = (F, β_{F} γ_{F}^{−1} : {1, …, n} ⟶ V_{F}).

Given a morphism (φ_{g}, φ̃) of ugraphs we have seen in Lemma 3.4 that we get a morphism P((φ_{g}, φ̃)) = (φ_{g}, φ̃) of pographs.

We have to show that condition (2) is satisfied. We have β_{F} := α_{F} and γ_{F} := id from the construction of P. Let i, j ∈ O_{F} be given with β_{F} (i) = α_{F} (i) and β_{F} (j) = α_{F} (j) contained in a common connected component of F. Assume that i = γ_{F} (i) ≤ γ_{F} (j) = j in {1, …, m}. Then φ̃(i) ≤ φ̃(j) in |α_{G}| hence also in {1, …, n}. This means γ_{G}φ̃(i) = φ̃(i) ≤ φ̃(j) = γ_{G}φ̃(j) in {1, …, n}.

Given a morphism (φ_{g}, φ̃) : (F, O_{F} , β_{F} , γ_{F}) ⟶ (G, O_{G}, β_{G}, γ_{G}) in Upograph. By the construction of P′ we have α_{F} = β_{F} γ_{F}^{−1} and α_{G} = β_{G}γ_{G}^{−1}. Define φ̃′ := γ_{G}φ̃γ_{F}^{−1} : |α_{F} | ⟶ |α_{G}|. Then φ_{g}α_{F} = φ_{g}β_{F} γ_{F}^{−1} = β_{G}φ̃γ_{F}^{−1} = β_{G}γ_{G}^{−1}φ̃′ = α_{G}φ̃′.

So it remains to show that φ̃′ : |α_{F} | ⟶ |α_{G}| is order preserving. Let i, j ∈ |α_{F} | with i ≤ j in |α_{F} | be given. Then i ≤ j in {1, …, m}, and α_{F} (i) and α_{F} (j) are in the same connected component in F. Let i′ := γ_{F}^{−1}(i) and j′ := γ_{F}^{−1}(j). Then i′, j′ ∈ O_{F} with β_{F} (i′) and β_{F} (j′) contained in a common connected component of F. Furthermore we have γ_{F} (i′) = i ≤ j = γ_{F} (j) hence γ_{G}φ̃(i′) ≤ γ_{G}φ̃(j′). Obviously α_{G}φ̃′(i) = β_{G}γ_{G}^{−1}φ̃′(i) = β_{G}φ̃(i′) = φ_{g}β_{F} γ_{F}^{−1}(i) = φ_{g}α_{F} (i) and α_{G}φ̃′(j) = φ_{g}α_{F} (j) are contained in a common connected component of G. Finally we have φ̃′(i) = γ_{G}φ̃(i′) ≤ γ_{G}φ̃(j′) = φ̃′(j) in {1, …, n} since γ_{G} is order preserving so φ̃′(i) ≤ φ̃′(j) in |α_{G}|.

It is clear that P and P′ are functors. Furthermore we have P′P = Id and PP′ ≅ Id given by the construction of the strong isomorphism in Proposition 2.6 which is an isomorphism in Upograph. □

The construction of Corollary 3.10 can be extended to morphisms as follows. Theorem 3.15. Let (F, O_{F} , β_{F}) and (G, O_{G}, β_{G}) be pographs and let (φ_{g}, g̃) be a morphism of pographs.

Then there exist update schedules γ_{F} : O_{F} ⟶ {1, …, m} and γ_{G} : O_{G} ⟶ {1, …, n} and a morphism of ugraphs (φ_{g}, φ̃) : (F, α_{F}) ⟶ (G, α_{G}) that restricts to the given morphism of pographs (φ_{g}, g̃).

Proof. This is a direct consequence of Proposition 3.8 and Corollary 3.9. □

4. Sequential Dynamical Systems on pographs

We have proved that every ugraph defines a pograph with update schedule unique up to strong isomorphism and conversely. Furthermore morphisms of ugraphs turn out to be special morphisms of pographs. We apply this now to SDS. Definition 4.1. A sequential dynamical system or an SDS on a pograph F

F = (F, (k[a]|a ∈ V_{F}), (f_{a}|a ∈ V_{F}))

consists of

(1) a finite pograph F,

(2) a family of sets (k[a]|a ∈ V_{F}) in Z,

(3) a family of local functions (f_{a} : k^{r} ⟶ k^{r}|a ∈ V_{F} , f_{a} local at a) in Z.

Given an SDS on a pograph and assume that we have an update schedule γ : O ⟶ {1, …, n} for the pograph. Then we can define a global update function as we did for an SDS over a ugraph:

f_{βγ^{−1}} := f_{βγ^{−1}(1)} ∘ … ∘ f_{βγ^{−1}(n)} : k^{r} ⟶ k^{r}.

For an SDS on a pograph without a given update schedule, however, it is not clear how to construct a global update function. So the following Proposition and its consequences are surprising and important.

Proposition 4.2. Let F be a finite sequential dynamical system on a pograph F. Let γ, η : O_{F} ⟶ {1, …, n} be update schedules. Then

f_{βγ^{−1}} = f_{βη^{−1}}.

Proof. For all i ∈ {1, …, n} let a_{i} := βγ^{−1}(i) and b_{i} := βη^{−1}(i). We want to show f_{a_{1}} ∘ … ∘ f_{a_{n}} = f_{b_{1}} ∘ … ∘ f_{b_{n}}.

For each j there is an i(= γη^{−1}(j)) such that b_{j} = a_{i} and conversely.

Claim: Given j, k ∈ {1, …, n} such that k < j and ηγ^{−1}(j) < ηγ^{−1}(k), then f_{βγ^{−1}(j)} ∘ f_{βγ^{−1}(k)} = f_{βγ^{−1}(k)} ∘ f_{βγ^{−1}(j)}. Let u := γ^{−1}(j) and v := γ^{−1}(k). Then γ(v) < γ(u) and η(u) < η(v). Since both maps γ and η are order preserving we get that u ≰ v and v ≰ u in the poset O_{F} hence {β(u), β(v)} ∉ E_{F}. So we get that f_{β(u)} ∘ f_{β(v)} = f_{β(v)} ∘ f_{β(u)} by Remark 1.1.

Assume now that we have already arranged a reordering of the update function such that

f_{a_{1}} ∘ … ∘ f_{a_{n}} = f_{b_{1}} ∘ … ∘ f_{b_{j−1}} ∘ f_{a_{l}} ∘ … ∘ f_{a_{m}}

where the f_{a_{l}}, …, f_{a_{m}} are those factors among the f_{a_{1}}, …, f_{a_{n}} that do not occur as factors f_{b_{1}}, …, f_{b_{j−1}} and where their product is taken in the same order as in f_{a_{1}}, …, f_{a_{n}}.

Let η^{−1}(j) = γ^{−1}(i) and thus b_{j} = a_{i} and f_{b_{j}} = f_{a_{i}}. We want to shift the local update function f_{b_{j}} = f_{a_{i}} in the right hand side of the equation towards the left. Given k with l ≤ k < i then ηγ^{−1}(i) = j < ηγ^{−1}(k) (because f_{b_{ηγ^{−1}(k)}} in the update function f_{b_{1}} ∘ … ∘ f_{b_{n}} does not occur in the partial product f_{b_{1}} ∘ … ∘ f_{b_{j−1}}). Thus f_{b_{j}} ∘ f_{a_{k}} = f_{a_{k}} ∘ f_{b_{j}}. So we can rearrange the update function to

f_{a_{1}} ∘ … ∘ f_{a_{n}} = f_{b_{1}} ∘ … ∘ f_{b_{j}} ∘ f_{a_{l′}} ∘ … ∘ f_{a_{m′}}.

By induction this completes the proof. □

Theorem 4.3. Let F be an SDS on a pograph. Then F has a well-defined global update function f_{β} := f_{βγ^{−1}} : k^{r} ⟶ k^{r}.

Proof. By Corollary 3.10 there is an update schedule γ. By Proposition 4.2 the global update function is independent of the choice of the update schedule γ. □

In a subsequent paper where we will define and study morphisms of SDS on pographs we will use this theorem and Theorem 3.15 to prove:

The construction of global update functions of SDS on pographs and its associated state graphs defines a functor to the category of dynamical systems and to the category of graphs. Remark 4.4. What we have proved is that any two update schedules of pographs give the same global update function. Furthermore, the number of different update schedules for a ugraph giving the same global update function is greater than or equal to the number of bijective order preserving maps O_{F} ⟶ {1, …, n}.

Actually we can prove more. Proposition 4.5. Let F be a graph and let α : {1, …, n} ⟶ V_{F} be an update schedule with canonical decomposition {1, …, n} ⟵^{γ} O_{F} ⟶^{β} V_{F}. If α̃ : {1, …, n} ⟶ V_{F} is an update schedule for F that does not factor through β then there is a structure of an SDS on F (in particular a family of state spaces and a family of local update functions) such that f_{α} ≠ fα̃.

We first need the following

Lemma 4.6. Let β : O ⟶ V_{F} and β̃: Õ ⟶ V_{F} be pographs on the same graph F. Assume there is a bijective order preserving map δ : O ⟶ Õ such that β̃δ = β. Then δ is an isomorphism of posets.

Proof. Let i ◁ j in Õ. Then {β̃(i), β̃(j)} ∈ E_{F}. Let u := δ^{−1}(i) and v := δ^{−1}(j). Then {β(u), β(v)} = {β̃δ(u), β̃δ(v)} = {β̃(i), β̃(j)} ∈ E_{F}, hence u ≤ v or v ≤ u. Since δ is order preserving we obtain u ≤ v hence δ^{−1}(i) ≤ δ^{−1}(j). Thus δ^{−1} is order preserving. □

Proof. of Proposition: Since α ≠ α̃ we can consider 3 cases.

Case 1: Let Im(α) ≠ Im(α̃). Without loss of generality assume a ∈ Im(α) \ Im(α̃). Then set f_{b} = id for all b ≠ a in V_{F}. Then the global update functions are fα̃ = id and f_{α} = f_{a}^{r} ≠ id for a suitable choice of f_{a}, hence f_{α} ≠ fα̃.

Case 2: Let Im(α) = Im(α̃) and assume there is an a ∈ Im(α) such that f_{α} contains r copies of f_{a} and fα̃ contains s ≠ r copies of f_{a}. Again set all f_{b} = id for b ≠ a. Then by a suitable choice of f_{a} we get f_{α} ≠ fα̃.

Case 3: Let Im(α) = Im(α̃) and let there be the same number of factors f_{a} in f_{α} resp. fα̃ for all a ∈ V_{F}. So fα̃ arises from f_{α} by a reordering of the factors. Thus there is a permutation σ : {1, …, n} ⟶ {1, …, n} such that α̃σ = α. We can choose σ on the preimage of each a ∈ E_{F} to be order preserving, since the orderings of factors f_{a} among each other in the global update function are irrelevant.

We use the decomposition of α and α̃ into (O_{F} , β, γ = id) and (Õ_{F} , β̃, γ = id) resp. as constructed in Theorem 2.1. Then σ may be considered as a map σ : O_{F} ⟶ Õ_{F}. Assume f_{α} = fα̃ for all choices of families of local update functions (f_{a}). We claim that σ : O_{F} ⟶ Õ_{F} is order preserving.

Let a, b ∈ V_{F} with {a, b} ∈ E_{F}. Assume that the subwords of f_{α} and fα̃ consisting of factors f_{a} and f_{b} are of the form f_{a}^{i_{1}}f_{b}^{i_{2}}f_{a}^{i_{3}} … f_{b}^{i_{r}} and f_{a}^{j_{1}}f_{b}^{j_{2}}f_{a}^{j_{3}} … f_{b}^{j_{s}} (with i_{k}, j_{k} > 0 except for i_{1}, i_{r}, j_{1}, j_{s} which may also be zero). We will show further down that there are choices for f_{a} and f_{b} such that f_{a}^{i_{1}}f_{b}^{i_{2}}f_{a}^{i_{3}} … f_{b}^{i_{r}} = f_{a}^{j_{1}}f_{b}^{j_{2}}f_{a}^{j_{3}} … f_{b}^{j_{s}} iff (i_{1}, …, i_{r}) = (j_{1}, …, j_{s}). This is equivalent to σ being order preserving on the preimage of {a, b} under α. Since we may choose f_{c} = id for all c ≠ a, b, the assumption f_{α} = fα̃ implies that σ is order preserving on the preimage of {a, b} under α.

Now we show under the given assumptions that σ is order preserving. Let i, j ∈ O_{F} with i ˙≺ j. Then i ≤ j (as numbers) and {α(i), α(j)} ∈ E_{F}. Define a := α(i) and b := α(j). Then α̃σ(i) = a and α̃σ(j) = b. Hence σ(i) ˙≺ σ(j) or σ(j) ˙≺ σ(i) in Õ_{F}. If σ(j) ˙≺ σ(i) holds, then σ is not order preserving on the preimage of {a, b} under α. Hence we have σ(i) ˙≺ σ(j) and thus σ is order preserving.

By Lemma 4.6 we find that α̃ factors through β : O_{F} ⟶ V_{F}. This is a contradiction to the assumption in the Proposition. So f_{α} ≠ fα̃ for some choice of a family of local update functions (f_{a}).

It remains to show that there are choices for f_{a} and f_{b} such that f_{a}^{i_{1}}f_{b}^{i_{2}}f_{a}^{i_{3}} … f_{b}^{i_{r}} = f_{a}^{j_{1}}f_{b}^{j_{2}}f_{a}^{j_{3}} … f_{b}^{j_{s}} iff (i_{1}, …, i_{r}) = (j_{1}, …, j_{s}). Take k[a] = k[b] = ℕ (or a suitable finite subset thereof). Define

f_{a}(…, x[a], …, x[b], …) = \begin{cases}(…, p · x[a], …, x[b], …) & if x[a] > x[b], \\ (…, q · x[b], …, x[b], …) & if x[a] ≤ x[b], \end{cases}

where p is the largest prime dividing x[a] and q is the smallest prime not dividing x[b]. Furthermore let

f_{b}(…, x[a], …, x[b], …) = \begin{cases}(…, x[a], …, q · x[a], …) & if x[a] ≥ x[b], \\ (…, x[a], …, p · x[b], …) & if x[a] < x[b], \end{cases}

where p is the largest prime dividing x[b] and q is the smallest prime not dividing x[a]. Then

f_{a}^{i_{1}}f_{b}^{i_{2}} … f_{a}^{i_{r−1}}f_{b}^{i_{r}}(…, 1, …, 1, …) = (…, 2^{i_{r}} · 3^{i_{r−1}} · . . . · p_{r−1}^{i_{2}} · p_{r}^{i_{1}}, …, 2^{i_{r}} · 3^{i_{r−1}} · . . . · p_{r−1}^{i_{2}}, …),

for i_{k} > 0. A similar argument holds for i_{1} = 0 and/or i_{r} = 0. This proves the claim and the Proposition. □

Corollary 4.7. The number of bijective order preserving maps O_{F} ⟶ {1, …, n} is a sharp lower bound for the number of different update schedules for a graph giving the same global update function.

Let F be a graph. We call two update schedules α, α′ : {1, …, n} ⟶ V_{F} equivalent, iff for all choices of local state spaces (k[a]|a ∈ V_{F}) and all choices of local update functions (f_{a}|a ∈ V_{F}) on the given graph F the global update functions f_{α} and f_{α′} are equal.

Corollary 4.8. There is a one-to-one correspondence between equivalence classes of update schedules of length n and poset models with n elements of the graph F.

5. On the Posets of Pographs

We have seen that the structure of SDS strongly depends on the underlying pographs. In this section we investigate which posets can occur as posets in pographs.

Definition 5.1. A pograph (F, O_{F} , β) is called rigid, if there is only one bijective map of posets γ : O_{F} ⟶ {1, …, n}. In other words, a pograph is rigid, if O_{F} has a unique extension to a total ordering.

An update schedule α : {1, …, n} ⟶ V_{F} of a graph F is called rigid if there is only one bijective map of posets γ : O_{F} ⟶ {1, …, n}, where O_{F} is induced by α.

Proposition 5.2. α is rigid if and only if O_{F} is totally ordered.

Proof. This follows from the fact that a poset has a unique extension to a total ordering if and only if it is already totally ordered. See [8, p. 17]. □

Thus for pographs with totally ordered poset O_{F} we have only one update schedule. The opposite observation is that a pograph with a discrete poset (no two elements can be compared) has n^{n} update functions β : O_{F} ⟶ {1, …, n}. They all give the same global update function. Examples 5.3. (1) A linear graph a_{1}, …, a_{n} with E_{F} = {{a_{i}, a_{i+1}} | i = 1, …, n − 1}

has a rigid update schedule α(i) = a_{i}. An example for such an SDS is a column of cars on a road a_{1}, …, a_{n} where each car determines its behavior or its local update function upon the preceding car. This gives a linear graph and the update schedule α cannot be changed without the risk of changing the global update function of the system.

(2) A linear graph with at least three vertices has a nonrigid update schedule. Let a, b, c be three consecutive vertices in F with edges {a, b} and {b, c}. Consider the rigid update schedule α with α(i) = a, α(i + 1) = b, and α(i + 2) = c. Define new update schedules α̃ by α̃(j) := α(j) for j ≠ i + 1, i + 2 and α̃(i + 1) = c, α̃(i + 2) = b and \overline{α} by \overline{α}(j) := α(j) for j ≠ i, i + 1, i + 2, and \overline{α}(i) = c, \overline{α}(i + 1) = a, \overline{α}(i + 2) = b. Then it is easy to see that both update schedules define the same poset O (as constructed in the proof of Theorem 2.1).

(3) The hypercube F = {(x_{1}, …, x_{n}) | x_{i} ∈ {0, 1}} with 2^{n} vertices has a rigid update schedule α : {1, …, 2^{n}} ⟶ F. It is well known that F is a Hamiltonian graph. By omitting the last edge in a Hamiltonian path we get a rigid update schedule α : {1, …, 2^{n}} ⟶ V_{F}.

(4) It is an easy exercise to show that hypercubes of dimension n ≥ 2 have nonrigid update schedules.

(5) An interesting example of a rigid update schedule is given in Example 2.4.

Now we show that any finite poset O can occur as a poset of a pograph. Proposition 5.4. 1) Let O be a finite poset. Let V be a set and β : O ⟶ V be a map such that i ◁ j implies β(i) ≠ β(j) for all i, j ∈ O. Then the Hasse diagram

E_{F} := {{β(i), β(j)} | i, j ∈ O : i ◁ j}

defines a graph F with vertex set V_{F} = V such that (F, O, β) is a pograph.

2) Let O be a finite poset. Let V be a set and β : O ⟶ V be a map such that i ◁ j implies β(i) ≠ β(j) for all i, j ∈ O. Then

E_{F} := {{β(i), β(j)} | i, j ∈ O : i < j and β(i) ≠ β(j)}

defines a graph F with vertex set V_{F} = V such that (F, O, β) is a pograph.

3) The graph constructed in 1) over β : O ⟶ V is the smallest subgraph of the complete graph on V such that (F, O, β) is a pograph. The graph constructed in 2) over β : O ⟶ V is the largest subgraph of the complete graph on V such that (F, O, β) is a pograph.

Proof. 1) We have to check that β : O ⟶ V_{F} is a pograph. By definition of the graph F we have for all i, j ∈ O

i ◁ j ⟺ {β(i), β(j)} ∈ E_{F} .

This implies both conditions (1) and (2).

2) Again we have to check that β : O ⟶ V_{F} is a pograph. By definition of the graph F we have for all i, j ∈ O such that β(i) ≠ β(j):

{β(i), β(j)} ∈ E_{F} ⟺ i < j ∨ j < i.

This implies also both conditions (1) and (2).

3) Let F be a graph with V_{F} = V and assume that (F, O, β) is a pograph. Let F_{min} be the graph constructed in 1) from the map β. Let {β(i), β(j)} be in F_{min}. Then i ◁ j hence {β(i), β(j)} is an edge in F by axiom (1).

Let F_{max} be the graph constructed in 2) from the map β. Let {β(i), β(j)} be in F. Then i < j (or j < i) by axiom (2). Hence {β(i), β(j)} is an edge in F_{max}. □

It is interesting to note that any graph F′ between F_{min} and F_{max} as constructed above (subgraph and supergraph on the same set of vertices) gives also a poset model β : O ⟶ V_{F′} as can be easily checked.

References

[1] C. L. Barrett, and C. M. Reidys, Elements of a Theory of Simulation, I: Sequential CA Over Random Graphs, Appl. Math. and Comput. 98, pp. 241–259, 1999.

[2] C. L. Barrett, H. S. Mortveit, and C. M. Reidys, Elements of a Theory of Computer Simulation II: Sequential Dynamical Systems, Appl. Math. and Comp. 107 (2–3). 121–136, 1999.

[3] C. L. Barrett, H. S. Mortveit, and C. M. Reidys, Elements of a Theory of Computer Simulation III: Equivalence of SDS, Appl. Math. and Comp. 122, 325–340, 2001.

[4] L. Garcia, A. Jarrah, and R. Laubenbacher, A Classification of Finite Dynamical Systems, preprint.

[5] R. Laubenbacher and B. Pareigis: Equivalence Relations on Finite Dynamical Systems, Adv. in Appl. Math. 26 (2001) 237–251.

[6] R. Laubenbacher and B. Pareigis: Decomposition and Simulation of Sequential Dynamical Systems. to appear in Adv. in Appl. Math..

[7] C. Reidys, Acyclic Orientations of Random Graphs, Adv. in Appl. Math 21, 181–192, 1998.

[8] T. Trotter, Combinatorics and Partially Ordered Sets, Johns Hopkins University Press, Baltimore, 1992.

Virginia Bioinformatics Institute, 1880 Pratt Drive, Blacksburg, VA 24061

E-mail address: reinhard@vbi.vt.edu

Math. Inst. d. Universität München, Theresienstr. 39, 80333 München, Germany

E-mail address: pareigis@lmu.de