Sequential dynamical system

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.

An SDS is constructed from the following components: It is convenient to introduce the Y-local maps Fi constructed from the vertex functions by 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 If the update sequence is a permutation one frequently speaks of a permutation SDS to emphasize this point.

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.

Note that the state of vertex 1 at time t=1 is used immediately.

This completes the update sequence, and one concludes that the Nor-SDS map sends the system state (0,0,0) to (1,0,0).