DECOMPOSITION AND SIMULATION OF SEQUENTIAL DYNAMICAL SYSTEMS

REINHARD LAUBENBACHER AND BODO PAREIGIS

Abstract. Sequential dynamical systems have been developed as a basis for a theory of computer simulation. This paper contains a generalization of this concept. The notion of morphism of sequential dynamical systems is introduced, formalizing the concept of simulating one system by another. Several examples of morphisms are given. Using the morphism concept, it is shown that every sequential dynamical system decomposes uniquely into a product of indecomposable systems.

Introduction

Computer simulation has become an important tool in the study of complex natural and human-made systems, from the biochemical network underlying cell metabolism to road traffic systems in our cities. A variety of simulation tools are available, ranging from discrete event simulations and differential-equations-based simulations, to stochastic simulations, and various hybrids of these.

Much insight has been gained into the structure as well as the dynamic behavior of complex systems through the use of simulations, and they provide an important basis for hypothesis generation, which may determine experimental setups. But simulation is by and large still an art form, with little theoretical guidance to its design, and mostly ad hoc methods for the analysis of the resulting output. Comparison of different simulations of the same system is difficult, as is the comparison of implementations of the same simulation on different platforms, especially of large-scale simulations. Many of the problems associated with simulation approaches require powerful scientific tools, however, as well as a rigorous methodology.

There exists a scattered collection of results and techniques that can be considered part of a newly emerging simulation science. An important contribution is the theory of sequential dynamical systems (SDS), a mathematical abstraction of a large class of computer simulations [2, 3, 4]. SDS theory is intended as a mathematical foundation for computer simulations that are representable as discrete dynamical systems. Theorems about SDS provide analysis tools for existing simulations and guidance for the design of new ones. Simulation practice has provided the inspiration for the definition of SDS and for the search for theorems about them. A fully developed SDS theory promises to provide answers to many theoretical questions about simulations. To the extent that the theory has been used in practice this promise has been fulfilled. In developing simulation science it is important, however, that the theory be guided by a close connection to and intimate knowledge of simulation practice, just as good simulations require intimate knowledge of the systems to be simulated.

Date: June 20, 2002.

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

This paper was written while the second author was visiting the Physical Science Laboratory of New Mexico State University (NMSU), Las Cruces, in 2001. He wishes to thank the Laboratory and all colleagues for their support and hospitality. The work of the first author was partially supported by funds from a partnership initiative between NMSU and Los Alamos National Laboratory.

Most systems of interest, whether biological, social, or technical, are too large to be simulated accurately. Even if such simulations can be run on a computer, the output is very difficult to analyze. Thus, the question arises how to replace a large system, or large simulation, by a smaller one, and how to relate their dynamics and properties. Such a replacement should come in the form of a “mapping” of some sort between SDS, which carries structural information. We will provide a theoretical framework for this question by defining the notion of a morphism of SDS. Morphisms will be closed under composition, and lead therefore to a category of SDS. Based on this framework we will investigate the notion of a morphism in this SDS category as a suitable tool for the simulation of one SDS by another. If such morphisms are indeed the correct way of relating SDS simulations, then a variety of modifications of simulations can be expressed as mathematical constructions, an important step toward the development of mathematical principles for simulation design.

As to the mathematical side of this theory we want to study the dynamical behavior of certain discrete dynamical systems encoded in the structure of the state space of the associated global update function of an SDS. The introduction of permissible maps or morphisms between SDS allows us to observe the effect of structural changes of an SDS on its dynamical behavior. The concept of morphism and category of SDS and other tools used in different categories will help us to eventually develop a mathematical structure theory of SDS and be able to fine tune the dynamic behavior of an SDS. Our approach uses tools from and brings new results to graph theory, discrete mathematics, and discrete dynamical systems theory. The categorical tools used in our approach help us to ask the right questions to understand the relationship between structure and behavior of SDS.

In this paper we describe a more general concept of SDS, and will call the “classical” concept a permutation SDS (PSDS). For the convenience of the reader we recall the PSDS concept.

Let k = {0, 1}. A permutation sequential dynamical system F on the set k^{n} of binary strings of length n can be thought of as a function

f : k^{n} ⟶ k^{n},

constructed from the following data:

(1) a finite graph F on n vertices,

(2) a family of “local” update functions f_{a} : k^{n} ⟶ k^{n}, one for each vertex a of F, which changes only the coordinate corresponding to a, and computes the binary state of vertex a. They are furthermore assumed to be symmetric in their inputs. These functions are local in the sense that they only depend on those variables which are connected to a in F.

(3) an “update schedule” π, which specifies an order on the vertices of F, represented by a permutation π ∈ S_{n}.

The function f is then constructed by composing the local functions according to the update schedule π, that is,

f = f_{π(n)} ∘ ⋯ ∘ f_{π(1)} : k^{n} ⟶ k^{n}.

The study of these systems leads to very interesting mathematical questions, independent of applications, and motivated [6], in which we began the development of a more general framework for PSDS. This framework is used in [5] to explore a setup for SDS in which the graph F is not explicit in the data. It naturally suggests a definition for the linearization of a finite system, such as certain types of SDS.

In this paper we generalize the notion of a permutation dynamical system to that of an SDS. To begin with, we allow the set k of states to be arbitrary, rather than just {0, 1}. In particular, k could be a subset of ℝ, e.g. the interval [0, 1]. This could lead to the notions of fuzzy and stochastic SDS. Secondly, we make no restrictions on the local functions f_{a}, with respect to symmetry. Most importantly, we use more general update schedules which allow the use of only a subset of all local functions in the construction of the global update function, as well as arbitrary repetitions of local update functions. This is very useful from the point of view of applications. For instance, SDS include global functions that simply permute the entries of a binary string. Such a function cannot be the global update function of a PSDS. This notion of SDS includes in particular PSDS.

The bulk of the paper is devoted to the study of special simulations of SDS by other SDS given by certain reasonable maps between these systems which will lead to the construction of morphisms of SDS, thereby eventually constructing a category SDS. From the point of view of applications a morphism from an SDS F to another SDS G should be thought of as a simulation of one system by the other. Two interpretations are of particular interest. A monomorphism should represent a simulation of G by F, then F is the smaller and more manageable system, F is a subsystem of G. An epimorphism should represent a simulation of F by G. Here G is the smaller system, G is a quotient system of F.

In our definition of morphisms we are guided by the desire to have sufficiently many morphisms available so that the category would possess finite products, and so that there should be sufficiently many isomorphisms to identify systems that should be considered isomorphic. To determine if two SDS F and G are isomorphic is not trivial in view of the very simple Example 2.5 (2). But if we know that F and G are isomorphic, then we can pick the easier looking model to study its dynamic behavior.

Furthermore morphisms should help us to find simpler models of SDS as explained below. A morphism φ : F ⟶ G of sequential dynamical systems should have the following properties in special cases. F should mimic to a certain extent the dynamical structure of G, but it should be simpler. For a given sequential dynamical system G we look for a simple sequential dynamical system F and a morphism φ, that maps a certain state of F into a start state of G, so that F has the “same” dynamical behavior as G starting at the given state. It would be nice if we could even give a freely generated sequential dynamical system F with this property. But that seems to be too complicated at present.

One could also consider the dual situation: for a given sequential dynamical system F together with a start state find a simple sequential dynamical system G that has the “same” dynamical behavior as F and find a morphism φ : F ⟶ G that maps the start state of F into G and that preserves the dynamical behavior.

Thus we want that a morphism of SDS should induce a morphism between their state spaces (phase spaces). That is, there should be a functor from this category to the category of directed graphs. This setup will then help to identify functorially dependent invariants of SDS, such as its associated global update function or its state space derived from the update function. Certain things may not be invariants of SDS such as the occurrence of certain states e.g. “diagonal states” (x, …, x) in limit cycles of its state space. The result is a rather complex definition of morphism, and we provide a list of examples motivating each of the ingredients.

This categorical setting allows a rigorous study of relations between SDS (and, in particular, of PSDS), in the form of morphisms between them. We show that SDS has products, and that every SDS can be decomposed uniquely into a finite product of indecomposable SDS.

1. Sequential Dynamical Systems

We first recall a few facts about graphs and permutation sequential dynamical systems.

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. Definition 1.1. A (loop free, undirected, finite) graph G = (V_{G}, E_{G}) consists of a finite set V_{G} of vertices and a subset E_{G} ⊆ P_{2}(X) of edges. Definition 1.2. Let F and G be graphs. A graph morphism φ : F ⟶ G consists of a map φ : V_{F} ⟶ V_{G} such that

∀{a, b} ∈ E_{F} : {φ(a), φ(b)} ∈ E_{G} or φ(a) = φ(b),

i.e. edges are either mapped to edges or they are ’collapsed’ to a vertex.

A subgraph F of a graph G consists of subsets V_{F} ⊆ V_{G} and E_{F} ⊆ E_{G}. The image of a graph morphism is a subgraph. A disjoint union of graphs is a graph. Every graph G can be decomposed into a disjoint union of connected components G_{(i)}. A connected subgraph of a graph is always contained in exactly one connected component of the graph. Every graph morphism maps connected components into connected subgraphs.

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

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

Throughout the paper we fix a subcategory Z of the category of sets. Let V_{G} = {a_{1}, …, a_{n}}. Let (k[a]|a ∈ V_{G}) be a family of sets (objects or “zets”) in Z. The set k[a] will be called the set of local states at a. Define

k^{n} := k[a_{1}] × … × k[a_{n}] = ∏_{a∈V_{G}} k[a],

the set of (global) states of G. We use the following notation. For a state x ∈ k^{n} and a vertex a ∈ V_{G} we write x[a] for the state of the vertex a or the a-th component of x so that

x = (x[a_{1}], …, x[a_{n}]).

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

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

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

where f^{i}(x[a_{1}], …, x[a_{n}]) ∈ k[a_{i}] depends only on the variables in the 1-neighborhood N(a_{i}) of the vertex a_{i}.

Definition 1.3. A permutation sequential dynamical system over the set of states k = {0, 1}, or a PSDS F = (F, (f_{a}), α) consists of

(1) a finite graph F with n vertices,

(2) a family of local functions (f_{a} : k^{n} ⟶ k^{n}|a ∈ V_{F} , f_{a} local at a), that are symmetric in the arguments,

(3) and a permutation α = (α(1), …, α(n)) = (α_{1}, …, α_{n}) ∈ S_{n} of the set V_{F} of vertices of F, called update schedule.

The global update function of a PSDS is the function

f = f_{α_{n}} ∘ … ∘ f_{α_{1}} : k^{n} ⟶ k^{n}.

Definition 1.4. A sequential dynamical system or an SDS^{1}, F = (F, (k[a]), (f_{a}), α) consists of

(1) a finite graph F with n vertices,

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

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

(4) and a word α = α_{F} = (α_{1}, …, α_{r}) ∈ V_{F}^{∗} in the Kleene closure of the set of vertices V_{G}, called update schedule (i.e. a map α : {1, …, r} ⟶ V_{F}).

The word α is used to define the global update function of an SDS as the function

f = f_{α_{r}} ∘ … ∘ f_{α_{1}} : k^{n} ⟶ k^{n}.

The length of the update schedule α = (α_{1}, …, α_{r}) is r. The global update function of an SDS defines its dynamical behavior, properties of limit cycles, transients, etc..

If we choose k[a] = {0, 1}, α a permutation in S_{n}, and assume that the f_{a} are symmetric in the arguments, then we obtain the definition of a permutation sequential dynamical system.

2. Morphisms of Sequential Dynamical Systems

In order to define a morphism of SDS we have to consider the following data of an SDS: the graph F, the local functions (f_{a}), the word α, and the sets of states (k[a]), all of which may be changed by maps. For the graph F, the word α, and the sets of states k[a] we shall introduce maps with certain compatibility requirements. The local functions f_{a} will occur in commutative diagrams. Definition 2.1. Let F = (F, (k[a]), (f_{i} : k^{n} ⟶ k^{n}), α) (with V_{F} = {a_{1}, …, a_{n}} and f_{i} = f_{a_{i}}) and G = (G, (k[b]), (g_{j} : k^{m} ⟶ k^{m}), β) be SDS. Let φ_{g} : G ⟶ F be a graph morphism, and (φ_{s}[b] : k[φ_{g}(b)] ⟶ k[b]|b ∈ V_{G}) be a family of maps in the category Z. Then φ_{g} and the family (φ_{s}[b]) induce an adjoint map on the state spaces as follows: consider the pairing

k^{n} × V_{F} ∋ (x, a) ↦ ⟨x, a⟩ := x[a] ∈ ⋃_{a∈V_{F}} k[a],

and similarly k^{m} × V_{G} ⟶ ⋃ k[b]. Then φ_{g} : G ⟶ F and (φ_{s}[b]) induce an adjoint map φ^{∗} : k^{n} ⟶ k^{m} with

(1)  ⟨φ^{∗}(x), b⟩ := φ_{s}[b](⟨x, φ_{g}(b)⟩)

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

or

φ^{∗}(x[a_{1}], …, x[a_{n}]) := (φ_{s}[b_{1}](x[φ_{g}(b_{1})]), …, φ_{s}[b_{m}](x[φ_{g}(b_{m})])).

Remark 2.2. Let (G, (k[b]), (g_{j} : k^{m} ⟶ k^{m}), β) be an SDS. Let {G_{(l)}} be the set of connected components of G. Let g_{i} : k^{m} ⟶ k^{m} and g_{j} : k^{m} ⟶ k^{m} be two local functions for the vertices a_{i}, a_{j} in different connected components, then g_{i}∘g_{j} = g_{j} ∘g_{i}, since both maps depend only on the 1-neighborhoods of a_{i} and a_{j} contained in the disjoint connected components. Similarly any two products of local functions f_{i_{1}} ∘…∘f_{i_{r}} all being defined over a connected component G_{(1)} and f_{j_{1}} ∘ … ∘ f_{j_{s}} all being defined over a connected component G_{(2)} commute.

Let F = (F, (k[a]), (f_{i} : k^{n} ⟶ k^{n}), α) and G = (G, (k[b]), (g_{j} : k^{m} ⟶ k^{m}), β) be SDS. As first components of a morphism φ : F ⟶ G we have already a map of graphs φ_{g} : G ⟶ F and a family of maps (φ_{s}[b] : k[φ_{g}(b)] ⟶ k[b]|b ∈ V_{G}) in Z (together with its adjoint map φ^{∗} : k^{n} ⟶ k^{m}). With the following examples we want to motivate the conditions that we have to impose on maps between words that relate α and β.

We want that morphisms between SDS should preserve the local and global dynamical behavior. This implies that morphisms between SDS lead to morphisms between the associated global update functions. The following diagram should commute:

[figure: k^{n}; k^{n}; f; k^{m}; k^{m}; g; φ^{∗}; φ^{∗}]

We use the word α = (α_{1}, …, α_{s}) to describe the global update function as f = f_{α_{s}} ∘ ⋯ f_{α_{1}} and β = (β_{1}, …, β_{t}) for g = g_{β_{t}} ∘ ⋯ g_{β_{1}}. We want to reduce the above diagram to similar conditions about the local update functions. The followings examples will show the most important points that have to be observed for this definition. Examples 2.3. In the following list of examples we refer to the graphs in Figure 1. We assume k[a] = k[b] = k for all a ∈ V_{F}, b ∈ V_{G}, and φ_{s}[b] = id for all b ∈ V_{G}.

(1) Let φ_{g} : G_{1} ⟶ F be the identity map on the vertices. Let F be defined with the word α = (abcd), and let G be defined with the word β = (abcd). If we require that the following diagrams commute

[figure: k^{n}; k^{n}; f_{α_{i}}; k^{m}; k^{m}; g_{β_{i}}; φ^{∗}; φ^{∗}]

then the diagram

[figure: k^{n}; k^{n}; f_{a}; k^{m}; k^{m}; g_{a}; φ^{∗}; φ^{∗}; k^{n}; k^{n}; f_{b}; k^{m}; k^{m}; g_{b}; φ^{∗}; φ^{∗}; k^{n}; k^{n}; f_{c}; k^{m}; k^{m}; g_{c}; φ^{∗}; k^{n}; k^{n}; f_{d}; k^{m}; k^{m}; g_{d}]

commutes, and thus we have a commutative diagram for the global update functions.

(2) Consider the graph morphism φ_{g} : G_{2} ⟶ F, given by the inclusion on the vertices. We use the words α = (abcd) and β = (abc). Then we are forced to require that the following diagram commutes.

[figure: k^{n}; k^{n}; f_{a}; k^{m}; k^{m}; g_{a}; φ^{∗}; φ^{∗}; k^{n}; k^{n}; f_{b}; k^{m}; k^{m}; g_{b}; φ^{∗}; φ^{∗}; k^{n}; k^{n}; f_{c}; k^{m}; k^{m}; g_{c}; φ^{∗}; k^{n}; k^{n}; f_{d}; k^{m}; k^{m}; id]

So we have to assume that the partial diagram concerning f_{d} commutes with the identity as lower arrow, since φ_{g}^{−1}(d) = ∅. Again we have that the diagram for the global update functions commutes.

(3) Use φ_{g} : G_{3} ⟶ F, with φ_{g}(a) = a and φ_{g}(b) = φ_{g}(c) = b, and α = (abcd), resp. β = (abc). Then we have to consider the following diagram:

[figure: k^{n}; k^{n}; f_{a}; k^{m}; k^{m}; g_{a}; φ^{∗}; φ^{∗}; k^{n}; k^{n}; f_{b}; k^{m}; k^{m}; g_{c}g_{b}; φ^{∗}; φ^{∗}; k^{n}; k^{n}; f_{c}; k^{m}; k^{m}; id; φ^{∗}; k^{n}; k^{n}; f_{d}; k^{m}; k^{m}; id]

Observe that there are no vertices being mapped into c, d ∈ V (F), but that the two vertices b and c in G_{3} are mapped to b in F. Obviously the order of g_{b} and g_{c} is important. So a map between the words of the two SDS should not only be compatible with the graph map but it should also be order preserving in some sense.

(4) Now we consider φ_{g} : G_{2} ⟶ F, resp. φ_{g} : G_{3} ⟶ F, sending a to a, b to b, and c to a, and α = (abcd), resp. β = (abc). Then we have to consider the following diagram:

[figure: k^{n}; k^{n}; f_{a}; k^{m}; k^{m}; g_{c}g_{a}; φ^{∗}; φ^{∗}; k^{n}; k^{n}; f_{b}; k^{m}; k^{m}; g_{b}; φ^{∗}; φ^{∗}; k^{n}; k^{n}; f_{c}; k^{m}; k^{m}; id; φ^{∗}; k^{n}; k^{n}; f_{d}; k^{m}; k^{m}; id]

Observe that the composition in the lower row gives g_{b}g_{c}g_{a}. In case of the graph G_{2} this is the global update function g = g_{c}g_{b}g_{a}, since b and c are in different connected components of the graph, so that g_{b} and g_{c} commute under composition. In the case of the graph G_{3}, however, these two local update functions do not commute in general, so that this construction should not give a morphism in our category, and we have to exclude it. This can be done by looking at order preserving maps from the subwords on the connected components of G_{2}, resp. G_{3}, to the word α on the graph F.

Now we fix some notation that we will use in the following definition.

Let β_{(l)} denote the subword of β whose letters belong to the connected component G_{(l)}. Let |β| denote the ordered set of indices {1, …, length of β} and let |β_{(l)}| denote the ordered subset of indices of β_{(l)} (in |β|).

Observe that the (unordered) set |β| decomposes into a disjoint union of the (unordered) sets |β_{(l)}|.

Definition 2.4. Let F = (F, (k[a]), (f_{i} : k^{n} ⟶ k^{n}), α) (with V_{F} = {a_{1}, …, a_{n}} and f_{i} = f_{a_{i}}) and G = (G, (k[b]), (g_{j} : k^{m} ⟶ k^{m}), β) (with V_{G} = {b_{1}, …, b_{m}}) be SDS.

A (Z-)morphism of sequential dynamical systems φ : (F, (k[a]), (f_{i} : k^{n} ⟶ k^{n}), α) ⟶ (G, (k[b]), (g_{j} : k^{m} ⟶ k^{m}), β) consists of

- a graph morphism φ_{g} : G ⟶ F (reverse direction!),

- a family of maps (φ_{s}[b] : k[φ_{g}(b)] ⟶ k[b] | b ∈ V_{G}, φ_{s}[b] ∈ Z),

- and a family of order preserving maps

φ̃_{(l)} : |β_{(l)}| ⟶ |α|

for each connected component G_{(l)} of G

such that

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

- if i ∈ |α| and \overline{φ}_{(l)}(i) := (β_{j}|φ̃_{(l)}(j) = i) is the subword of β_{(l)} mapped into α_{i} then the diagram

[figure: k^{n}; k^{n}; f_{α_{i}}; k^{m}; k^{m}; ∏_{l} ∏_{\overline{φ}_{(l)}(i)} g_{β_{j}}; φ^{∗}; φ^{∗}]

commutes, where the product ∏_{\overline{φ}_{(l)}(i)} g_{β_{j}} is taken in the order of the entries in the subword \overline{φ}_{(l)}(i). (If \overline{φ}_{(l)}(i) is the empty word, then the product is assumed to be the identity map.)

In order to further motivate this definition we give a few examples that show that the conditions are necessary for our further studies. Example 2.5. (1) This example shows that two very simple SDS that should be isomorphic, are indeed isomorphic. Here we use k[a] = k[b] = k and we need the set maps φ_{s}[b] : k ⟶ k.

Let F = {a} be the one vertex graph. For i ∈ k define the set map p_{i} : k ⟶ k to be the projection of k onto the element i ∈ k. Let i, j ∈ k with i ≠ j. Let F = (F, (k), (p_{i} : k ⟶ k), (a)) and G = (F, (k), (p_{j} : k ⟶ k), (a)). Then F ≅ G.

We define the isomorphism φ : F ⟶ G by φ_{g} = id : {a} ⟶ {a}, φ_{s}[a] = π : k ⟶ k where π is some bijective map from k to k with π(i) = j. Finally let φ̃_{(1)} = id. Then φ is a morphism of SDS with inverse ψ = (id, π^{−1}, id). In fact we have φ_{g}(β_{1}) = id(a) = α_{φ̃_{(1)}(1)} and the diagram

[figure: k; k; p_{i}; k; k; p_{j}; φ^{∗}=π; φ^{∗}=π]

commutes.

(2) Consider the following two SDS F = (F, (k), (f_{i}), α) and G = (F, (k), (g_{i}), α) over k = {0, 1} where V_{F} = {a, b} and E_{F} = {{a, b}}. Let

\begin{matrix}f_{a}(x_{1}, x_{2}) = (x_{2}, x_{2}), & f_{b}(x_{1}, x_{2}) = (x_{1}, \overline{x_{2}}), \\ g_{a}(x_{1}, x_{2}) = (\overline{x_{2}}, x_{2}), & g_{b}(x_{1}, x_{2}) = (x_{1}, \overline{x_{2}}). \end{matrix}

The update schedule α is arbitrary. It is not clear if these SDS are isomorphic, in particular if they give isomorphic state spaces as described in section 3. If we define φ : F ⟶ G by φ_{g} = id, φ_{s}[a] = τ, φ_{s}[b] = id, and φ̃_{(1)} = id then this is an isomorphism since the diagrams

[figure: k^{2}; k^{2}; f_{a}; k^{2}; k^{2}; g_{a}; φ^{∗}=τ×id; φ^{∗}=τ×id; k^{2}; k^{2}; f_{b}; k^{2}; k^{2}; g_{b}; φ^{∗}=τ×id; φ^{∗}=τ×id]

commute.

(3) We determine the set of all morphisms in some very simple cases. Let k[a] = k[b] = k = {0, 1}. We consider 4 SDS all defined on the trivial one point graph {a} and with the trivial one letter update schedule a. Let

I := (a, k, id : k ⟶ k, a),
T := (a, k, τ : k ⟶ k, a),
P_{0} := (a, k, p_{0} : k ⟶ k, a),
P_{1} := (a, k, p_{1} : k ⟶ k, a),

where τ is the interchange map sending 1 to 0 and 0 to 1, and the p_{i} are the maps in the preceding example. In order to find isomorphic SDS, we have to find out if the diagram

[figure: k; k; f; k; k; g; φ^{∗}; φ^{∗}]

commutes. If f ≠ g this is only the case for f = p_{0} and g = p_{1} (or conversely). Thus we have that three of the four SDS are nonisomorphic. More generally we have for the number of morphisms

|Mor(I, I)| = 4 |Mor(T , T )| = 2 |Mor(P_{0}, P_{0})| = 2 |Mor(P_{1}, P_{1})| = 2
|Mor(I, T )| = 0 |Mor(T , I)| = 2 |Mor(P_{0}, P_{1})| = 2 |Mor(P_{1}, P_{0})| = 2
|Mor(I, P_{0})| = 1 |Mor(P_{0}, I)| = 2 |Mor(T , P_{0})| = 1 |Mor(P_{0}, T )| = 0
|Mor(I, P_{1})| = 1 |Mor(P_{1}, I)| = 2 |Mor(T , P_{1})| = 1 |Mor(P_{1}, T )| = 0.

(4) We consider now some morphisms that only depend on the choice of the order preserving maps φ̃_{(l)} but that are defined on the same morphism φ_{g} of graphs.

Let F be defined by V_{F} = {a_{1}, a_{2}} = {u, v} (with u = a_{1}, v = a_{2}) and E_{F} = {{u, v}}, and let α = (u, v, u). Let k[u] = k[v] = k. At this time we do not fix the local functions f_{u}, f_{v} : k^{2} ⟶ k^{2}. Furthermore let G be defined by V_{G} = {b_{1}} = {w} and E_{G} = ∅, let k[w] = k, and let β = (w, w). For G we also do not fix the local function g_{w} : k ⟶ k. Define a graph morphism φ_{g} : G ⟶ F by φ_{g}(w) = u. We also fix φ_{s}[w] : k ⟶ k to be the identity. Then φ^{∗} : k^{2} ⟶ k is the projection onto the first component pr_{1}, since φ^{∗}(x[u], x[v]) = x[φ_{g}(w)] = x[u]. Both graphs have only one connected component. Our definitions give ordered sets |α| = {1, 2, 3}, |β| = {1, 2} = |β_{(1)}|.

For φ̃_{(l)} : |β_{(1)}| ⟶ |α| or φ̃_{(l)} : {1, 2} ⟶ {1, 2, 3} we have the choice among three “order preserving maps of ordered multisets” that satisfy the first axiom for morphisms:

[figure: w; u; w; v; u; w; u; w; v; u; w; u; w; v; u]

We want to establish conditions so that these three maps define morphisms of SDS.

Case 1: We have φ̃_{(1)}(1) = 1 and φ̃_{(1)}(2) = 1. So the following diagrams must commute:

[figure: k^{2}; k^{2}; f_{α_{1}}=f_{u}; k; k; g_{β_{2}}g_{β_{1}}=g_{w}^{2}; pr_{1}; pr_{1}; k^{2}; k^{2}; f_{α_{2}}=f_{v}; k; k; id; pr_{1}; k^{2}; k^{2}; f_{α_{3}}=f_{u}; k; k; id; pr_{1}]

Conditions for the local maps so that this becomes a morphism of SDS are f_{u} = id and g_{w}^{2} = id.

Case 2: We have φ̃_{(1)}(1) = 1 and φ̃_{(1)}(2) = 3. So the following diagrams must commute:

[figure: k^{2}; k^{2}; f_{α_{1}}=f_{u}; k; k; g_{β_{1}}=g_{w}; pr_{1}; pr_{1}; k^{2}; k^{2}; f_{α_{2}}=f_{v}; k; k; id; pr_{1}; k^{2}; k^{2}; f_{α_{3}}=f_{u}; k; k; g_{β_{1}}=g_{w}; pr_{1}]

Conditions for the local maps so that this becomes a morphism of SDS are f_{u}(x[u], x[v]) = (g_{w}(x[u]), x[v]).

Case 3: We have φ̃_{(1)}(1) = 3 and φ̃_{(1)}(2) = 3. So the following diagrams must commute:

[figure: k^{2}; k^{2}; f_{α_{1}}=f_{u}; k; k; id; pr_{1}; pr_{1}; k^{2}; k^{2}; f_{α_{2}}=f_{v}; k; k; id; pr_{1}; k^{2}; k^{2}; f_{α_{3}}=f_{u}; k; k; g_{β_{2}}g_{β_{1}}=g_{w}^{2}; pr_{1}]

Conditions for the local maps so that this becomes a morphism of SDS are f_{u} = id and g_{w}^{2} = id.

(5) If k[a] = [0, 1] ⊂ ℝ is the closed unit interval and k[b] = \{0, \frac{1}{2}, 1\}, then any SDS with state spaces k[a] can be considered as a probabilistic or fuzzy dynamical system, where each vertex has states between 0 and 1. Some interesting local update functions f_{a} : k^{n} ⟶ k^{n} are the ones where the a-th component is the product of all states in a 1-neighborhood of x_{a}. A discretization of such a system is obtained by taking the identity maps for φ_{g} and φ̃, and as maps between the states the maps that send 0 to 0, 1 to 1, and all other values to \frac{1}{2}.

Theorem 2.6. The sequential dynamical systems (F, (k[a]), (f_{a}), α) together with the morphisms of SDS form a category SDS.

Proof. The associativity and unit laws are easily checked. So the proof follows from □

Proposition and Definition 2.7. Let

φ : F = (F, (k[a]), (f_{1}, …, f_{n}), α) ⟶ G = (G, (k[b]), (g_{1}, …, g_{m}), β)

and

ψ : G = (G, (k[b]), (g_{1}, …, g_{m}), β) ⟶ H = (H, (k[c]), (h_{1}, …, h_{r}), γ)

be two morphisms of SDS. Then the composition

ψ ∘ φ : F ⟶ H

is a morphism of SDS, where the composition ψ ∘ φ consists of

- the composite of the associated graph morphisms φ_{g}ψ_{g} : H ⟶ F,

- the family of maps

(2)  (ψ ∘ φ)_{s}[c] := ψ_{s}[c]φ_{s}[ψ_{g}(c)] for all c ∈ H,

- and the composite of the corresponding families of order preserving maps ψ̃_{(l)} : |γ_{(l)}|⟶|β| and φ̃_{(l′)} : |β_{(l′)}|⟶|α|.

Proof. The composite of the graph morphisms is obviously again a graph morphism.

Since connected components of the graph H are mapped into connected components of the graph G, we find a connected component G_{(l′)} into which the connected component H_{(l)} is mapped hence we get ψ̃_{(l)} : |γ_{(l)}|⟶|β_{(l′)}| so that the order preserving maps can be composed to

{ \atop (φψ)}_{(l)} : |γ_{(l)}| \underrightarrow{ψ̃_{(l)}} |β_{(l′)}| \underrightarrow{φ̃_{(l′)}} |α|.

The first axiom is easily verified: let H_{(l)} be a connected component of H. Let j ∈ |γ_{(l)}|. Then φ_{g}ψ_{g}(γ_{j}) = φ_{g}(β_{ψ̃_{(l)}(j)}) = α_{φ̃_{(l′)}ψ̃_{(l)}(j)} = α_{{ \atop (φψ)}_{(l)}}(j).

Now observe that

⟨(ψ ∘ φ)^{∗}(x), c⟩ = (ψ ∘ φ)_{s}[c](⟨x, (ψ ∘ φ)_{g}(c)⟩)
= ψ_{s}[c]φ_{s}[ψ_{g}(c)](⟨x, φ_{g}ψ_{g}(c)⟩)
= ψ_{s}[c](⟨φ^{∗}(x), ψ_{g}(c)⟩)
= ⟨ψ^{∗}φ^{∗}(x), c⟩

which implies (ψ ∘ φ)^{∗} = ψ^{∗}φ^{∗}. So we have to show that the diagram

[figure: k^{n}; k^{n}; f_{α_{i}}; k^{m}; k^{m}; ∏ g_{β_{j}}; k^{r}; k^{r}; ∏ h_{γu}; φ^{∗}; φ^{∗}; ψ^{∗}; ψ^{∗}]

commutes. The middle arrow can be decomposed into ∏_{l} ∏_{\overline{φ}_{(l)}(i)} g_{β_{j}} = g_{β_{t}} … g_{β_{1}} and for each g_{β_{j}} we get associated diagrams from ψ so that the total diagram

[figure: k^{n}; k^{n}; f_{α_{i}}; k^{m}; k^{m}; g_{β_{1}}; k^{m}; k^{m}; g_{β_{t}}; k^{r}; k^{r}; ∏_{l} ∏_{\overline{ψ}_{(l)}(1)} h_{γ_{j}}; …; k^{r}; k^{r}; ∏_{l} ∏_{\overline{ψ}_{(l)}(t)} h_{γ_{j}}; …; φ^{∗}; φ^{∗}; ψ^{∗}; ψ^{∗}; ψ^{∗}; ψ^{∗}]

commutes. From the considerations we made about the composition of ψ̃_{(l)} and φ̃_{(l′)} it follows that the product on the lower line is ∏_{l} ∏_{\overline{φψ}_{(l)}(i)} h_{γ_{j}} by using the fact from Remark 2.2 that local functions on different connected components commute:

∏_{l} ∏_{\overline{ψ}_{(l)}(t)} h_{γ_{j}} … ∏_{l} ∏_{\overline{ψ}_{(l)}(1)} h_{γ_{j}} = ∏_{l} ( ∏_{\overline{ψ}_{(l)}(t)...\overline{ψ}_{(l)}(1)} h_{γ_{j}} ) = ∏_{l} ( ∏_{\overline{φψ}_{(l)}(i)} h_{γ_{j}} ) ,

where \overline{ψ}_{(l)}(t) … \overline{ψ}_{(l)}(1) is the concatenation of the corresponding subwords. This is a subword of γ since ψ̃_{(l)} is order preserving and (β_{t}, …, β_{1}) is a subword of β.

Hence the diagrams

[figure: k^{n}; k^{n}; f_{α_{i}}; k^{r}; k^{r}; ∏_{l} ∏_{\overline{φψ}_{(l)}(i)} h_{γ_{j}}; (ψ∘φ)^{∗}; (ψ∘φ)^{∗}]

commute. □

Since the composition of morphisms of SDS is defined by composition of certain set maps, isomorphisms of SDS consists of certain bijective set maps. This is useful to construct or identify isomorphisms. In fact Example 2.5 (2) was constructed in such a way.

3. State Spaces

Any function f : k^{n} ⟶ k^{n} defines a finite directed graph with vertex set k^{n} and directed edges (x, f(x)) for all x ∈ k^{n}, called the state space of f : k^{n} ⟶ k^{n}. A morphism from f : k^{n} ⟶ k^{n} to g : k^{m} ⟶ k^{m} is a commutative diagram

[figure: k^{n}; k^{n}; f; k^{m}; k^{m}; g; h; h].

In this way every morphism of ’functions’ induces a morphism of the associated state spaces in the category of directed graphs. So we have a covariant functor from ’functions’ to the full subcategory S of state spaces in the category of directed graphs.

Let F = (F, (k[a]), (f_{1}, …, f_{n}), α) be an SDS with update function f_{α} : k^{n} ⟶ k^{n}, f_{α} := f_{α_{1}} … f_{α_{n}}. In this section we show that there is a covariant functor

S : SDS ⟶ S,

given by assigning to an SDS the state space of its update function. Lemma 3.1. A morphism φ : F ⟶ G of SDS induces a commutative diagram

[figure: k^{n}; k^{n}; f_{α}; k^{m}; k^{m}; g_{β}; φ^{∗}; φ^{∗}] ,

that is a morphism of the update functions. Furthermore φ induces a graph morphism S(φ) between the state space of f_{α} : k^{n} ⟶ k^{n} and the state space of g_{β} : k^{m} ⟶ k^{m}.

Proof. The diagram

[figure: k^{n}; k^{n}; f_{α_{1}}; …; k^{n}; k^{n}; f_{αr}; k^{m}; k^{m}; ∏_{l} ∏_{\overline{φ}_{(l)}(1)} g_{β_{j}}; …; k^{m}; k^{m}; ∏_{l} ∏_{\overline{φ}_{(l)}(r)} g_{β_{j}}; φ^{∗}; φ^{∗}; φ^{∗}; φ^{∗}]

commutes. It remains to show that

g_{β} = g_{β_{s}} … g_{β_{1}} = ∏_{l} ∏_{\overline{φ}_{(l)}(r)} g_{β_{j}} … ∏_{l} ∏_{\overline{φ}_{(l)}(1)} g_{β_{j}}.

Since the g_{β_{j}} are local functions, the functions g_{β_{i}} and g_{β_{j}} commute if their vertices β_{i} and β_{j} are in different connected components of G. Hence it suffices to show that

∏_{β_{j}∈β_{(l)}} g_{β_{j}} = ∏_{β_{j}∈\overline{φ}_{(l)}(r)} g_{β_{j}} … ∏_{β_{j}∈\overline{φ}_{(l)}(1)} g_{β_{j}}.

In fact the g’s may be grouped together according to connected components without changing their product. But this equation holds since the map φ̃_{(l)} : |β_{(l)}| ⟶ |α| is order preserving. The rest of the statement follows trivially. □

Thus φ induces a morphism of state spaces

S(φ) : S(F) ⟶ S(G).

This proves the following theorem.

Theorem 3.2. Passage to state spaces induces a covariant functor

S : SDS ⟶ S.

Observe that this functor extracts and clarifies the dynamic behavior of an SDS.

4. Products of Sequential Dynamical Systems

Theorem 4.1. The category SDS has finite products.

Proof. Let F = (F, (k[a]), (f_{1}, …, f_{n}), α) and G = (G, (k[b]), (g_{1}, …, g_{m}), β) be SDS. Define the product

H = (H, (k[c]), (h_{1}, …, h_{n+m}), γ) = F × G

as follows. Let H = F ˙∪G be the disjoint union of the graphs F and G, with vertex set V_{F} ˙∪V_{G}. Observe that the graph components F and G are disconnected. Define k[c] := k[a] for any c = a ∈ V_{F} ⊆ V_{H} and k[c] := k[b] for any c = b ∈ V_{G} ⊆ V_{H}. Now define

h_{c} : k^{n+m} = k^{n} × k^{m} ⟶ k^{n+m}

as follows. For c = a ∈ V_{F} define h_{c} := f_{a} × id, and for c = b ∈ V_{G} we set h_{c} := id × g_{b}. Finally, we define the update schedule as the concatenation of words

γ = αβ.

Next we define a projection morphism

pr_{G} : F × G ⟶ G,

and similarly a projection into F. Let pr_{G,g} : G ⟶ F ∪ G be the inclusion, and pr_{G,s}[b] := id for all b ∈ V_{G}. Observe that pr_{G}^{∗} : k^{n+m} = k^{n} × k^{m} ⟶ k^{m} is the projection. Finally let p̃r_{G(l)}(j) := (length of α) + j. To verify that in this way we indeed obtain a morphism of SDS, observe that we have commutative diagrams

[figure: k^{n} × k^{m}; k^{n} × k^{m}; f_{a}×id; k^{m}; k^{m}; id; pr_{G}^{∗}; pr_{G}^{∗}] [figure: k^{n} × k^{m}; k^{n} × k^{m}; id×g_{b}; k^{m}; k^{m}; g_{b}; pr_{G}^{∗}; pr_{G}^{∗}] .

This shows that the second condition of a morphism is satisfied and that pr_{G} is indeed a morphism of SDS.

It remains to verify the universal property of the product. Suppose we are given an SDS K = (K, (k[d]), (k_{d}), δ) and morphisms φ : K ⟶ F and ψ : K ⟶ G. We need to show that there is a unique morphism

ω : K ⟶ F × G,

such that pr_{F} ∘ ω = φ and pr_{G} ∘ ω = ψ. Define

ω_{g} : F ∪ G ⟶ K

to be equal to φ_{g}, resp. ψ_{g}, on the component F, resp. G. Define ω_{s}[c] := φ_{s}[a] for c = a ∈ V_{F} and ω_{s}[c] := ψ_{s}[b] for c = b ∈ V_{G}. Since a connected component of F × G is a connected component of either F or G the order preserving map ω̃_{(l)} is determined by either φ̃_{(l)} or ψ̃_{(l)}.

Then clearly (pr_{F}∘ω)_{g} = φ_{g} and (pr_{G}∘ω)_{g} = ψ_{g}. Furthermore (pr_{F}∘ω)_{s}[a] = pr_{F,s}[a]ω_{s}[pr_{F,g}(a)] = ω_{s}[a] = φ_{s}[a] for all a ∈ V_{F} and similarly (pr_{G} ∘ ω)_{s}[b] = ψ_{s}[b].

It is clear now that ω is a morphism uniquely determined by φ and ψ. □

Lemma 4.2. Let F = (F, (k[a]), (f_{a}), α) be an SDS. If α_{i} and α_{i+1} are in different connected components of F, then

(F, (k[a]), (f_{a}), (α_{1}, …, α_{i+1}, α_{i}, …, α_{r}))

is isomorphic to F.

Proof. Define φ : F ⟶ (F, (k[a]), (f_{a}), (α_{1}, …, α_{i+1}, α_{i}, …, α_{r})). Use φ_{g} := (id : F ⟶ F) and φ_{s}[a] = id. Let α_{i} ∈ F_{(1)} and α_{i+1} ∈ F_{(2)}. Then let φ̃_{(2)}(i) := i + 1 and φ̃_{(1)}(i + 1) := i and φ̃_{(l)} := id otherwise. This is obviously a canonical isomorphism. □

Thus the update schedule α of any SDS F may be rearranged according to the connected components of F and this gives a canonically isomorphic SDS. Theorem 4.3. (1) An SDS is indecomposable (w.r.t. products) if and only if the under-

lying graph is connected.

(2) Any SDS is uniquely isomorphic to the product of its connected components, and the connected components are uniquely determined.

Proof. If F is a proper product then the underlying graph F is not connected. If F has more than one connected component, then by the preceding lemma it is canonically isomorphic to the product of its connected components as constructed above. □

To study morphisms of SDS it suffices to know the morphisms of the form φ : F ⟶ G where G is indecomposable or connected. This holds since

Mor(F, G_{(1)} × … × G_{(r)}) ≅ ∏ Mor(F, G_{(i)}).

5. Decomposition of Morphisms

Theorem 5.1. Let F = F_{1} × … × F_{n} with indecomposable components F_{i} and let G be indecomposable. Let φ : F ⟶ G be a morphism. Then there is a uniquely determined component F_{i} and a uniquely determined morphism φ_{i} : F_{i} ⟶ G such that

(φ : F ⟶ G) = (φ_{i}pr_{i} : F ⟶ F_{i} ⟶ G).

Therefore

Mor(F_{1} × … × F_{n}, G) ≅ ⋃_{i=1}^{n} Mor(F_{i}, G).

Proof. These assertions follow from the construction of the product and the fact that the image of a connected graph is connected. □

An indecomposable SDS must be considered in some sense as an autonomous system. So an SDS may be considered as a parallel system of several connected components. The above theorem also implies that every morphism φ : F ⟶ G, where F and G are arbitary SDS, can be described by a family of morphisms φ_{j} : F_{i_{j}} ⟶ G_{j}, where the F_{i_{j}} are suitable indecomposable components of F, and the G_{j} run through all r indecomposable components of G. So we could write

φ = (φ_{1}, …, φ_{r}).

Therefore it is sufficient only to study morphisms between indecomposable SDS.

6. Equalizers

Example 6.1. We want to give an example of a nontrivial equalizer in the category SDS. This will also give us some examples and show the great variety of morphisms between fairly small SDS.

Let G := ((b), (k), (g_{b} = id_{b}), β = (b, b)) be an SDS on the one vertex graph. The local and global update function is the identity id : k ⟶ k. Finally the update schedule is a two letter word (b, b).

Let H := ((b), (k), (h_{b} = τ), γ = (b, b)) be an SDS with local function τ : k ⟶ k, the transposition τ(0) = 1, τ(1) = 0.

We construct two morphisms φ, φ′ : G ⟶ H by

\begin{matrix}φ_{g}(b) = b, & φ̃(1) = 1, & φ̃(2) = 1; \\ φ′_{g}(b) = b, & φ̃′(1) = 2, & φ̃′(2) = 2. \end{matrix}

Observe that the numbers 1 and 2 are the indices or positions of the letters in the word (b, b). Furthermore we use φ_{s}[b] = φ′_{s}[b] := id : k ⟶ k.

In order to check that these are morphisms we only have to show the second property of morphisms, namely that the two diagrams

[figure: k; k; g_{b}=id; k; k; h_{b}^{2}=id; φ^{∗}=id; φ^{∗}=id; k; k; g_{b}=id; k; k; id; φ^{∗}=id; φ^{∗}=id]

commute. The first diagram arises from the counterimage of the first letter of β = (b, b) consisting of two instances of the letter b, and the second diagram arises from the counterimage of the second letter of β = (b, b) that is empty. Similarly we show for φ′ that the diagrams

[figure: k; k; g_{b}=id; k; k; id; φ′^{∗}=id; φ′^{∗}=id; k; k; g_{b}=id; k; k; h_{b}^{2}=id; φ′^{∗}=id; φ′^{∗}=id]

commute.

Let K = ((b), (k), (l_{b} = id), (b)) be an SDS and define a morphism ι : K ⟶ G by ι(b) = b (reverse direction!) and ι̃(1) = 1 = ι̃(2). Since the diagram

[figure: k; k; l_{b}=id; k; k; g_{b}^{2}=id; ι^{∗}=id; ι^{∗}=id]

commutes, ι is a morphism and we have morphisms

[figure: K; G; ι; H; φ; φ′] .

We have φι = φ′ι since K has only one element components. We claim that (K, ι) is an equalizer of the pair (φ, φ′).

Let F = (F, (k[a]), (f_{i}), α) be an SDS and ψ : F ⟶ G be a morphism such that φψ = φ′ψ. We have to show that there is a unique morphism ν : F ⟶ K such that ιν = ψ. Let ψ_{g}(b) := a ∈ V_{F}, and let ψ̃(1) = i and ψ̃(2) = j, i.e. α_{i} = a = α_{j}. From φψ = φ′ψ we get ψ̃φ̃ = ψ̃φ̃′ and hence i = ψ̃φ̃(1) = ψ̃φ̃′(1) = j. Furthermore we have ψ^{∗} = ψ_{s}[b]pr_{a} : k^{n} ⟶ k[a] ⟶ k[b], and we have commutative diagrams

[figure: k^{n}; k^{n}; f_{a}; k; k; g_{b}=id; ψ^{∗}; ψ^{∗}; and; k^{n}; k^{n}; f_{a′}; k; k; id; ψ^{∗}; ψ^{∗}]

for all a′ ≠ a in F.

Now define ν : F ⟶ K by ν_{g}(b) := a, ν_{s}[b] = ψ_{s}[b], and ν̃(1) := i = j. This is obviously the only choice if we want to get ιν = ψ. Then we have ν^{∗} = ν_{s}[b]pr_{a} : k^{n} ⟶ k and the diagrams

[figure: k^{n}; k^{n}; f_{a}; k; k; l_{a}=id; ν^{∗}; ν^{∗}; k^{n}; k^{n}; f_{a′}; k; k; id; ν^{∗}; ν^{∗}]

commute, hence ι is the unique morphism such that ιν = ψ. So (K, ι) is an equalizer.

For the next two remarks we will assume Z = {k, id_{k}}. Remark 6.2. We want to show that, in general, there are no equalizers in the category of SDS. Let G = (G, (k[b]), (g_{b}), β) and H = (H, (k[c]), (h_{c}), γ) be the following SDS

- V_{G} := {a, b, c, d}, E_{G} := {{a, b}, {c, d}},
- k[b] := k = {0, 1} for all b ∈ V_{G},
- g_{b} := id for all b ∈ V_{G},
- β := (a, b, c, d) = (b_{1}, b_{2}, b_{3}, b_{4}).
- V_{H} := {a}, E_{F} := ∅,
- k[c] := k = {0, 1} for all c ∈ V_{H},
- h_{c} := id for all c ∈ V_{H},
- γ := (a) = (c_{1}).

Let φ, ψ : G ⟶ H be two morphisms given by

- φ_{g}(a) := a, ψ_{g}(a) := c,
- φ_{s}[a] := id =: ψ_{s}[a],
- φ̃(1) := 1, ψ̃(1) := 3.

We want to find an equalizer ρ : E ⟶ G of these two morphisms (i.e. φρ = ψρ and (E, ρ) universal w.r.t. this property).

As a test object we use the SDS F = (F, (k[a]), (f_{a}), α) defined as follows

- V_{F} := {a, b, d}, E_{F} := {{a, b}, {a, d}},
- k[a] := k = {0, 1} for all a ∈ V_{F},
- f_{a} := id for all a ∈ V_{F},
- α := (a, b, d) = (a_{1}, a_{2}, a_{3}).

The following two morphisms σ, τ : F ⟶ G should serve as test morphisms. They are given by

- σ_{g}(a) = σ_{g}(c) := a, σ_{g}(b) := b, σ_{g}(d) = d,
τ_{g}(a) = τ_{g}(c) := a, τ_{g}(b) := d, τ_{g}(d) = b,
- σ_{s}[a] := id =: τ_{s}[a] for all a ∈ V_{G},
- σ̃(1) := 1, σ̃(2) := 2, σ̃(3) := 1, σ̃(4) := 3,
τ̃(1) := 1, τ̃(2) := 3, τ̃(3) := 1, τ̃(4) := 2.

Then it is easy to see that σφ = σψ and τφ = τψ.

Assume that we have an equalizer ρ : E ⟶ G of φ and ψ. Then ρ_{g} must have the following images ρ_{g}(a) = ρ_{g}(c) =: ā (since ρ_{g}φ_{g} = ρ_{g}ψ_{g}), ρ_{g}(b) =: b̄, and ρ_{g}(d) =: d̄in V_{E}. Furthermore let ρ̃(1) =: i_{1}, ρ̃(2) =: i_{2}, ρ̃(3) =: i_{3}, and ρ̃(4) =: i_{4}. Then we have i_{1} = ρ̃(1) = ρ̃φ̃(1) = ρ̃ψ̃(1) = ρ̃(3) = i_{3}. Since ρ̃ is order preserving on the connected components, we get i_{1} ≤ i_{2} and i_{1} ≤ i_{4}. Since all of i_{1}, i_{2}, i_{4} map into a connected component of the graph E (they map into ā, b̄, d̄ resp.) we must have i_{2} and i_{4} comparable in the order of |δ|, the update schedule of E.

The morphisms σ and τ have unique factorizations σ = ρσ_{0} and τ = ρτ_{0} through the equalizer. Now σ̃_{0}(i_{2}) = σ̃(2) = 2 and σ̃_{0}(i_{4}) = σ̃(4) = 3. Since σ̃_{0} is order preserving we get i_{2} < i_{4}.

With the same argument for τ we get i_{2} > i_{4} a contradiction. Hence there cannot exist an equalizer for φ, ψ. Remark 6.3. In this context and with Z = {k, id_{k}} it might appear as if O = ((a), (k), (id), (a)) is an initial object in SDS. This is not the case since this SDS does not admit a morphism into any SDS with update functions not the identity on the diagonal in k^{n}, the diagram

[figure: k; k; id; k^{n}; k^{n}; f_{α}; Δ; Δ]

does not commute. To complete our study of products we have, however, the empty product. Lemma 6.4. The SDS (∅, ∅ = (), ∅ = (), ∅ = ()) is a final object in SDS.

Proof. There is a unique morphism of graphs ∅ ⟶ F and the diagram

[figure: k^{n}; k^{n}; f_{i}; {∗}; {∗}; id]

commutes. □

7. Simulations and their Effects on State Spaces

As we mentioned in the introduction, we consider a morphism φ : F ⟶ G as a simulation if φ is a monomorphism – then G is simulated by F – or, if φ is an epimorphism – then F is simulated by G. We will only consider those monomorphisms φ where φ_{g} is surjective on the set of vertices, and the φ_{s}[b] are injective. We will call them injective monomorphisms. Lemma 7.1. If φ : F ⟶ G is an injective monomorphism, then φ^{∗} : k^{n} ⟶ k^{m} is an injective map.

Proof. Let φ^{∗}(x_{1}, …, x_{n}) = φ^{∗}(y_{1}, …, y_{n}). Then

\begin{matrix}(φ_{s}[b_{1}](x[φ_{g}(b_{1})]), …, φ_{s}[b_{m}](x[φ_{g}(b_{m})])) \\ = (φ_{s}[b_{1}](y[φ_{g}(b_{1})]), …, φ_{s}[b_{m}](y[φ_{g}(b_{m})])). \end{matrix}

Hence, for all i = 1, …, m, we get φ_{s}[b_{i}](x[φ_{g}(b_{i})]) = φ_{s}[b_{i}](y[φ_{g}(b_{i})]). Since the φ_{s}[b_{i}] are injective we get that x[φ_{g}(b_{i})] = y[φ_{g}(b_{i})]. Now, φ_{g} is surjective, so we get (x_{1}, …, x_{n}) = (y_{1}, …, y_{n}). □

Considering epimorphisms, we will only consider those φ : F ⟶ G, where φ_{g} is injective on the set of vertices, and the φ_{s}[b] are surjective. We will call them surjective epimorphisms. Lemma 7.2. If φ : F ⟶ G is a surjective epimorphism, then φ^{∗} : k^{n} ⟶ k^{m} is a surjective map.

Proof. Let (y[b_{1}], …, y[b_{m}]) ∈ k^{m}. Then there is an m-tuple

(z[φ_{g}(b_{1})], …, z[φ_{g}(b_{m})]) ∈ k[φ_{g}(b_{1})] × … × k[φ_{g}(b_{m})],

such that (φ_{s}[b_{1}](z[φ_{g}(b_{1})]), …, φ_{s}[b_{m}](z[φ_{g}(b_{m})])) = (y[b_{1}], …, y[b_{m}]), since the φ_{s}[b_{i}] are surjective. Define x[a_{i}] := z[φ_{g}(b_{j})] ∈ k[a_{i}], if φ_{g}(b_{j}) = a_{i}, and x[a_{i}] arbitrary if a_{i} ∉ Im(φ_{g}). The x[a_{i}] = z[φ_{g}(b_{j})] are well defined since φ_{g} is injective, so that there is a (x[a_{1}], …, x[a_{n}]), such that

(x[φ_{g}(b_{1})], …, x[φ_{g}(b_{m})]) = (z[φ_{g}(b_{1})], …, z[φ_{g}(b_{m})]),

and thus φ^{∗} is surjective. □

Proposition 7.3. Let φ : F ⟶ G be an injective monomorphism, and let S(φ) : S(F) ⟶ S(G) be the graph morphism of the associated state spaces. Then

(1) S(φ) maps each limit cycle of S(F) bijectively onto a limit cycle of S(G);

(2) S(φ) is injective on the set of limit cycles;

(3) S(φ) maps transients injectively into transients, preserving endpoints.

Proof. The three statements are clear, since S(φ) is injective on the set of vertices. □

Proposition 7.4. Let φ : F ⟶ G be a surjective epimorphism, and let S(φ) : S(F) ⟶ S(G) be the graph morphism of the associated state spaces. Then

(1) S(φ) maps each limit cycle of length n of S(F) onto a limit cycle of length t of S(G), where t divides n;

(2) S(φ) maps the set of limit cycles of S(F) onto the set of limit cycles of S(G); (3) if two nodes of a transient in S(F) of distance n + 1 are mapped into the same node

of S(G), then the path between the two nodes in S(F) is mapped onto a limit cycle of length t in S(G), where t divides n.

Proof. Again, the three statements follow from the fact that S(φ) : S(F) ⟶ S(G) is surjective on the set of vertices. □

The two propositions show what kind of information about the dynamical behavior of some SDS is preserved if it is simulated by another SDS.

References

[1] C. L. Barrett, R. Thord, and C. M. Reidys, Knowledge and Networks in a Dynamical Economy, in Simulations in Decision Making for Socio-technical Systems, M. Beckman and B. Johansson and F. Snickars and R. Thord (eds.), Springer Verlag, New York, 1998.

[2] 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.

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

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

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

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

Virginia Bioinformatics Institute, Blacksburg, VA, 24061

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

Mathematisches Institut, Universität München, Theresienstr. 39, D-80333 München, Germany

E-mail address: pareigis@rz.mathematik.uni-muenchen.de