Sequential dynamical system

Sequential dynamical systems (SDSs) are a class of graph dynamical systems. They are discrete dynamical systems which generalize many aspects of for example classical cellular automata, and they provide a framework for studying asynchronous processes over graphs. The analysis of SDSs uses techniques from combinatorics, abstract algebra, graph theory, dynamical systems and probability theory.

Definition

An SDS is constructed from the following components:

• A finite graph Y with vertex set v[Y] = {1,2, ... , n}. Depending on the context the graph can be directed or undirected.

• A state x_v for each vertex v of Y taken from a finite set K. The system state is the n-tuple x = (x₁, x₂, ... , x_n), and x[v] is the tuple consisting of the states associated to the vertices in the 1-neighborhood of v in Y (in some fixed order).

• A vertex function f_v for each vertex v. The vertex function maps the state of vertex v at time t to the vertex state at time t + 1 based on the states associated to the 1-neighborhood of v in Y.

• A word w = (w₁, w₂, ... , w_m) over v[Y].

It is convenient to introduce the Y-local maps F_i constructed from the vertex functions by

$F_{i}(x)=(x_{1},x_{2},\ldots ,x_{i-1},f_{i}(x[i]),x_{i+1},\ldots ,x_{n})\;.$

The word w specifies the sequence in which the Y-local maps are composed to derive the sequential dynamical system map F: Kⁿ → Kⁿ as

$[F_{Y},w]=F_{w(m)}\circ F_{w(m-1)}\circ \cdots \circ F_{w(2)}\circ F_{w(1)}\;.$

If the update sequence is a permutation one frequently speaks of a permutation SDS to emphasize this point.

Example

Consider the triangle graph consisting simply of three connected nodes A,B,C.

In this example let the set of possible states be boolean i.e. {0,1}.

Assign an initial state e.g. A=1, B=1, C=0

As an example let the functions (using boolean arithmetic) for each node be: new(A)=B+C, new(B)=A+B, new(C)=C

Let the permutation be BCA, i.e. first of all B is updated using the new(B) function then C is updated with new(C) then A with new(A).

The states would then evolve as follows: step 0: A=1, B=1, C=0 step 1: B=0, C=0, A=0 : in natural order A=0, B=0, C=0 In this example we have immediately arrived at a fixed point, as applying the functions again leaves the states unchanged.

Starting from a different initial state: step 0: A=0, B=1, C=0 step 1: B=1, C=0, A=1 : in natural order A=1, B=1, C=0 step 2: B=0, C=0, A=0 : in natural order A=0, B=0, C=0

Phase space

A configuration is a list or vector consisting of the states of all the nodes. In the first of the above examples the initial configuration is 110 and then it changes to 000.

A phase space diagram is a directed graph consisting of a node for each possible configuration, A directed edge (or arrow) in the phase space represents the result of applying the functions. 010 would have an arrow to 110 which would have an arrow to 000 in the above example.

The main goal in the study of SDSs is to deduce the structure of the phase space from the underlying graph, functions and update order.

See also

• Graph dynamical system
• Boolean network
• Gene regulatory network
• Dynamic Bayesian network

References

• Henning S. Mortveit, Christian M. Reidys (2008). An Introduction to Sequential Dynamical Systems. Springer. ISBN 0387306544.
• Predecessor and Permutation Existence Problems for Sequential Dynamical Systems
• Genetic Sequential Dynamical Systems