グラフダイナミカルシステム
グラフダイナミカルシステムは以下の構成要素から構成される。
節点の集合v[Y] = {1,2, ... , n}をもつある有限グラフ Y. 方向ありかなしかという文脈に依存。
有限集合Kから得たYのそれぞれの節点vに対するある状態xv。系の状態とはn-タプル x = (x1, x2, ... , xn), であり x[v] はYにおいてvの1近傍にある頂点に関連する状態からなるタプルである(ある一定の順序で)。
節点関数とはfvである. 節点関数はYにおけるvの1近傍に関連する状態に基づいて、tにおけるvの状態をt + 1にマッピングする。
個々の頂点の状態の写像を行うメカニズムを指定した更新スキームが離散力学系を引き起こすようなFとは、F: K → K である。
位相空間は節点集合Kと方向付き辺(x, F(x))からなる写像F: K → Kを持つダイナミカルシステムに関連付けられる。位相空間の構造はグラフY、vertex functions (fi)i、更新スキームによって支配される。この分野の研究は、システムの構成要素の構造に基づいて位相空間の特性を推測しようとするものである。解析は局所から大域へという性格を持つ。
例えば、更新方式が頂点関数を同期的に適用するものであれば、GCAのクラスが得られる。この場合、グローバル写像F: K → K は以下で与えられる。
F ( x ) v = f v ( x [ v ] ) . {\displaystyle F(x)_{v}=f_{v}(x[v])\;.}
このクラスは、古典的あるいは標準的なセル・オートマトンが正則グラフあるいは格子上で定義・研究され、頂点関数が同一であることが一般に仮定されているので、一般化セルオートマトンと呼ばれる。
.
確率的グラフダイナミカルシステムに移行すると、一般に、(1) マルコフ連鎖の研究(GDSの構成要素に支配される特定の構造を持つ)に導かれること、(2) 結果として得られるマルコフ連鎖は指数関数的に状態数が増えて大きくなる傾向があること、の2点がこの種の系における一般的事実として示されている。確率的GDSの研究の中心的な目標は、縮小モデルを導出できるようにすることである。
また、頂点関数が確率的である場合についても考えることができる。 例: function stochastic GDS. 例えば、ランダムブールネットワークは、同期更新方式を用いた関数型確率的GDSの例である。ただし、状態空間はK = {0, 1}。有限確率セルオートマトン(PCA)は関数逐次GDSの別の例である。原則として、Interacting particle systems(IPS)は有限と無限の確率セルオートマトンをカバーするが、実際には、IPSの研究は、状態空間により興味深いトポロジーを導入することができるため、主に無限の場合に関係している。