Sequential dynamical system

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]


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • List of dynamical systems and differential equations topics — This is a list of dynamical system and differential equation topics, by Wikipedia page. See also list of partial differential equation topics, list of equations. Contents 1 Dynamical systems, in general 2 Abstract dynamical systems 3 …   Wikipedia

  • Combinatorics and dynamical systems — The mathematical disciplines of combinatorics and dynamical systems interact in a number of ways. The ergodic theory of dynamical systems has recently been used to prove combinatorial theorems about number theory which has given rise to the field …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Système dynamique séquentiel —   Cette page se comprend mieux après la lecture de Théorie des graphes. Un système dynamique séquentiel (SDS, « sequential dynamical system » en anglais) est un formalisme décrivant la façon dont l état des sommets d un graphe …   Wikipédia en Français

  • Network dynamics — is the study of networks that change in time. These networks could be from the fields of biology, sociology, economics, computer science, graph theory etc. For a dynamical systems approach to network dynamics, see sequential dynamical system. See …   Wikipedia

  • Hidden Markov model — Probabilistic parameters of a hidden Markov model (example) x mdash; states y mdash; possible observations a mdash; state transition probabilities b mdash; output probabilitiesA hidden Markov model (HMM) is a statistical model in which the system …   Wikipedia

  • Dynamic network analysis — (DNA) is an emergent scientific field that brings together traditional social network analysis (SNA), link analysis (LA) and multi agent systems (MAS) within network science and network theory. There are two aspects of this field. The first is… …   Wikipedia

  • Análisis de redes — Saltar a navegación, búsqueda El estudio de las propiedades estructurales y su optimización así como su dinámica son objeto del análisis de redes El análisis de redes es el área encargada de analizar las redes mediante la teoría de redes… …   Wikipedia Español

  • Kalman filter — Roles of the variables in the Kalman filter. (Larger image here) In statistics, the Kalman filter is a mathematical method named after Rudolf E. Kálmán. Its purpose is to use measurements observed over time, containing noise (random variations)… …   Wikipedia

  • Network theory — For network theory of the regulation of the adaptive immune system see Immune network theory For the sociological theory, see Social network Network theory is an area of computer science and network science and part of graph theory. It has… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”