连续动力系统
此词条暂由彩云小译翻译，翻译字数共579，未经人工整理和审校，带来阅读不便，请见谅。
thumbnail|right|Phase space of the 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.
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.
序列动力系统是一类图动力系统。它们是离散动力系统，概括了经典细胞自动机等许多方面，为研究图上的异步过程提供了一个框架。对 SDSs 的分析使用了组合学、抽象代数、图论、动力系统和概率论的技术。
Definition
An SDS is constructed from the following components:
An SDS is constructed from the following components:
= = Definition = = SDS 由以下组件构成:
- 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 xv for each vertex i of Y taken from a finite set K. The system state is the n-tuple x = (x1, x2, ... , xn), 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 fi 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 = (w1, w2, ... , wm) over v[Y].
- 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 xv for each vertex i of Y taken from a finite set K. The system state is the n-tuple x = (x1, x2, ... , xn), 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 fi 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 = (w1, w2, ... , wm) over v[Y].
- 顶点集 v [ y ] = {1,2，... ，n }的有限图 y。根据上下文，图可以是有向的或无向的。
- 取自有限集 k 的 y 的每个顶点 i 的状态 xv。系统状态是 n 元组 x = (x1，x2，... ，xn) ，x [ i ]是元组，由 y 中 i 的1- 邻域中与顶点相关的状态组成(按某种固定顺序)。
- 每个顶点 i 的顶点函数 fi。顶点函数将时间 t 的顶点 i 的状态映射到时间 t + 1的顶点状态，其基础是与 y 中 i 的1- 邻域相关的状态。
- 单词 w = (w1，w2，... ，wm)/v [ y ]。
It is convenient to introduce the Y-local maps Fi constructed from the vertex functions by
It is convenient to introduce the Y-local maps Fi constructed from the vertex functions by
介绍了由顶点函数构造的 y 局部映射 Fi 的简便方法
- [math]\displaystyle{ F_i (x) = (x_1, x_2,\ldots, x_{i-1}, f_i(x[i]), x_{i+1}, \ldots , x_n) \;. }[/math]
- F_i (x) = (x_1, x_2,\ldots, x_{i-1}, f_i(x[i]), x_{i+1}, \ldots , x_n) \;.
- 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: Kn → Kn as
The word w specifies the sequence in which the Y-local maps are composed to derive the sequential dynamical system map F: Kn → Kn as
单词 w 指定组成 y 局部映射的顺序，从而导出顺序的动力系统映射 f: Kn → Kn 为
- [math]\displaystyle{ [F_Y ,w] = F_{w(m)} \circ F_{w(m-1)} \circ \cdots \circ F_{w(2)} \circ F_{w(1)} \;. }[/math]
- [F_Y ,w] = F_{w(m)} \circ F_{w(m-1)} \circ \cdots \circ F_{w(2)} \circ F_{w(1)} \;.
- [ f _ y，w ] = f _ { w (m)}循环 f _ { w (m-1)}循环 c 点 f _ { w (2)}循环 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 to a sequential dynamical system with map F: Kn → Kn is the finite directed graph with vertex set Kn and directed edges (x, F(x)). The structure of the phase space is governed by the properties of the graph Y, the vertex functions (fi)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.
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: Kn → Kn is the finite directed graph with vertex set Kn and directed edges (x, F(x)). The structure of the phase space is governed by the properties of the graph Y, the vertex functions (fi)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.
如果更新序列是置换序列，则经常提到置换 SDS 以强调这一点。与映射 f: Kn → Kn 的序列动力系统相关的相空间是顶点集 Kn 和有向边(x，f (x))的有限有向图。相空间的结构由图 y 的性质、顶点函数(fi) i 和更新序列控制。SDS 的大部分研究试图根据系统成分的结构推断相空间特性。
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 : K3 → 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.
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 : K3 → 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.
= = 实例 = = 考虑这样一种情况: y 是顶点集{1,2,3}和无向边{1,2} ，{1,3}和{2,3}(一个三角形或三圆形) ，顶点状态从 k = {0,1}的图。对于顶点函数，使用 nor (x，y，z) = (1 + x)(1 + y)(1 + z)(1 + z)定义的对称布尔函数，nor: K3→ k。因此，函数 nor 返回值1的唯一情况是所有参数都为0。选择 w = (1,2,3)作为更新序列。从时间 t = 0时的初始系统状态(0,0,0)开始，计算时间 t = 1时的顶点1状态为 nor (0,0,0) = 1。时间 t = 1时顶点2的状态 nor (1,0,0) = 0。注意，在时间 t = 1时，顶点1的状态被立即使用。接下来，得到时间 t = 1时顶点3的状态为 nor (1,0,0) = 0。这就完成了更新序列，并得出结论: Nor-SDS 映射将系统状态(0,0,0)发送到(1,0,0)。通过 SDS 映射的应用程序将系统状态(1,0,0)转换为(0,1,0)。
See also
- Graph dynamical system
- Boolean network
- Gene regulatory network
- Dynamic Bayesian network
- Petri net
布尔图动态系统网络基因调控网络动态贝氏网路 Petri 网
References
- Henning S. Mortveit, Christian M. Reidys (2008). An Introduction to Sequential Dynamical Systems. Springer. ISBN 978-0387306544.
- Predecessor and Permutation Existence Problems for Sequential Dynamical Systems
- Genetic Sequential Dynamical Systems
- Predecessor and Permutation Existence Problems for Sequential Dynamical Systems
- Genetic Sequential Dynamical Systems
序列动力系统
- 遗传序列动力系统的前驱和置换存在性问题
Category:Combinatorics Category:Graph theory Category:Networks Category:Abstract algebra Category:Dynamical systems
范畴: 组合学范畴: 图论范畴: 网络范畴: 抽象代数范畴: 动力系统
This page was moved from wikipedia:en:Sequential dynamical system. Its edit history can be viewed at 连续动力系统/edithistory