Sequential dynamical system

Sequential dynamical systems (SDSs) are a class of discrete dynamical systems and generalize many aspects of for example classical cellular automata, and 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.

Sequential dynamical systems (SDSs) are a class of discrete dynamical systems and generalize many aspects of for example classical cellular automata, and 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 i of Y taken from a finite set K. The system state is the n-tuple x = (x 1 , x 2 , ... , x n ), and x[i] is the 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 i for each vertex i. The vertex function maps the state of vertex i at time t to the vertex state at time t + 1 based on the states associated to the 1-neighborhood of i in Y. A word w = (w 1 , w 2 , ... , 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 n → K n 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. The phase space associated with a sequential dynamical system with map F: K n → K n is the finite directed graph with vertex set K n 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 i ) i , 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 3 → 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== Boolean network Dynamic Bayesian network Gene regulatory network Graph dynamical system Petri net ==References== Predecessor and Permutation Existence Problems for Sequential Dynamical Systems Genetic Sequential Dynamical Systems

Text derived from https://en.wikipedia.org/w/index.php?oldid=1372898936 under CC BY-SA 4.0; modifications have been made.