Sequential dynamical system

Sequential dynamical systems (SDSs) are a class of discrete dynamical systems which generalize many aspects of systems such as cellular automata, and provide a framework for studying dynamical processes over graphs.

SDSs are used in the analysis and modeling of network dynamics as well as their computer simulations. Techniques from combinatorics, abstract algebra and graph theory are used to study properties of SDS such as reversibility, the structure of fixed points and periodic orbits, equivalence, morphisms and reduction.

Definition

An SDS consists of a graph where each node is assigned an initial state and a function for updating the state. In addition there is a list of nodes giving the order in which the functions should be applied. This order list is usually referred to as a permutation of the nodes.

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 thenC is updated with new(C) then A with new(A).

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

Starting from a different initial state:step 0: A=0, B=1, C=0step 1: B=1, C=0, A=1 : in natural order A=1, B=1, C=0step 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.

ee also

*Boolean network
*Gene regulatory network
*Dynamic Bayesian network

References

*
* [http://www.emis.de/journals/DMTCS/pdfpapers/dmAB0106.pdf Predecessor and Permutation Existence Problems for Sequential Dynamical Systems]
* [http://arxiv.org/pdf/math.DS/0603370 Genetic Sequential Dynamical Systems]