Graph Dynamical System - Sequential Dynamical Systems (SDS)

Sequential Dynamical Systems (SDS)

If the vertex functions are applied asynchronously in the sequence specified by a word w = (w₁, w₂, ..., w_m) or permutation = (, ) of v one obtains the class of Sequential dynamical systems (SDS). In this case it is convenient to introduce the Y-local maps F_i constructed from the vertex functions by

The SDS map F = : Kn → Kn is the function composition

If the update sequence is a permutation one frequently speaks of a permutation SDS to emphasize this point.

Example: Let Y be the circle graph on vertices {1,2,3,4} with edges {1,2}, {2,3}, {3,4} and {1,4}, denoted Circ₄. Let K={0,1} be the state space for each vertex and use the function nor₃ : K3 → K defined by nor₃(x, y, z) = (1 + x)(1 + y)(1 + z) with arithmetic modulo 2 for all vertex functions. Using the update sequence (1,2,3,4) then the system state (0, 1, 0, 0) is mapped to (0, 0, 1, 0). All the system state transitions for this sequential dynamical system are shown in the phase space below.