View source for Sequential dynamical system

{{Short description|Class of graph dynamical systems}}
[[File:SDSphase1.png|thumbnail|right|Phase space of the sequential dynamical system]]

'''Sequential dynamical systems''' ('''SDSs''') are a class of [[Graph dynamical system|graph dynamical system]]s. 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 [[Graph theory|graphs]]. The analysis of SDSs uses techniques from [[Combinatorics|combinatorics]], [[Abstract algebra|abstract algebra]], [[Graph theory|graph theory]], [[Dynamical system|dynamical system]]s and [[Probability theory|probability theory]].

==Definition==
An SDS is constructed from the following components:

<blockquote>
* 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<sub>v</sub>'' for each vertex ''i'' of ''Y'' taken from a finite set ''K''. The ''system state'' is the ''n''-tuple ''x'' = (''x''<sub>1</sub>, ''x''<sub>2</sub>, ... , ''x<sub>n</sub>''), and ''x''[''i''] is the [[Tuple|tuple]] consisting of the states associated to the vertices in the 1-neighborhood of ''i'' in ''Y'' (in some fixed order).
* A ''vertex function'' ''f<sub>i</sub>'' for each vertex ''i''. The vertex function maps the state of vertex ''i'' at time ''t'' to the vertex state at time ''t''&nbsp;+&nbsp;1 based on the states associated to the 1-neighborhood of ''i'' in ''Y''.
* A word ''w'' = (''w''<sub>1</sub>, ''w''<sub>2</sub>, ... , ''w<sub>m</sub>'') over ''v''[''Y'']. 
</blockquote>

It is convenient to introduce the ''Y''-local maps ''F<sub>i</sub>'' constructed from the vertex functions by

: <math>F_i (x) = (x_1, x_2,\ldots, x_{i-1}, f_i(x[i]), x_{i+1}, \ldots , x_n) \;. </math>

The word ''w'' specifies the sequence in which the ''Y''-local maps are composed to derive the sequential dynamical system map ''F'': ''K<sup>n</sup> → K<sup>n</sup>'' as

: <math>[F_Y ,w] = F_{w(m)} \circ F_{w(m-1)} \circ \cdots \circ F_{w(2)} \circ F_{w(1)} \;. </math>

If the update sequence is a permutation one frequently speaks of a ''permutation SDS'' to emphasize this point. 
The ''phase space'' associated to a sequential dynamical system with map ''F'': ''K<sup>n</sup> → K<sup>n</sup>'' is the finite directed graph with vertex set ''K<sup>n</sup>'' and directed edges (''x'', ''F''(''x'')). The structure of the phase space is governed by the properties of the graph ''Y'', the vertex functions (''f<sub>i</sub>'')''<sub>i</sub>'', and the update sequence ''w''. A large part of SDS research seeks to infer phase space properties based on the structure of the system constituents.

==Example==
Consider the case where ''Y'' is the graph with vertex set {1,2,3} and undirected edges {1,2}, {1,3} and {2,3} (a triangle or 3-circle) with vertex states from ''K'' = {0,1}. For vertex functions use the symmetric, boolean function nor : ''K<sup>3</sup> → K'' defined by nor(''x'',''y'',''z'') = (1+''x'')(1+''y'')(1+''z'') with boolean arithmetic. Thus, the only case in which the function nor returns the value 1 is when all the arguments are 0. Pick ''w'' = (1,2,3) as update sequence. Starting from the initial system state (0,0,0) at time ''t'' = 0 one computes the state of vertex 1 at time ''t''=1 as nor(0,0,0) = 1. The state of vertex 2 at time ''t''=1 is nor(1,0,0) = 0. Note that the state of vertex 1 at time ''t''=1 is used immediately. Next one obtains the state of vertex 3 at time ''t''=1 as nor(1,0,0) = 0. This completes the update sequence, and one concludes that the Nor-SDS map sends the system state (0,0,0) to (1,0,0). The system state (1,0,0) is in turned mapped to (0,1,0) by an application of the SDS map.

==See also==
*[[Graph dynamical system]]
*[[Physics:Boolean network|Boolean network]]
*[[Biology:Gene regulatory network|Gene regulatory network]]
*[[Dynamic Bayesian network]]
*[[Petri net]]

==References==
* {{cite book | author=Henning S. Mortveit, Christian M. Reidys | title=An Introduction to Sequential Dynamical Systems | publisher=Springer | year=2008 | isbn=978-0387306544}}
*[http://www.emis.de/journals/DMTCS/pdfpapers/dmAB0106.pdf Predecessor and Permutation Existence Problems for Sequential Dynamical Systems]
*[https://arxiv.org/abs/math.DS/0603370 Genetic Sequential Dynamical Systems]

[[Category:Combinatorics]]
[[Category:Graph theory]]
[[Category:Networks]]
[[Category:Abstract algebra]]
[[Category:Dynamical systems]]

{{Sourceattribution|Sequential dynamical system}}