Elements of a theory of simulation III: equivalence of SDS

In the development of mathematical foundations for a theory of simulation, a certain class of discrete sequential dynamical systems (SDS) is of particular importance. These systems which we refer to as SDS consist of: (a) a graph Y with vertex set {1,2,..., n}, where each vertex has associated a binary state, (b) a vertex labeled set of functions F-i,F-Y : F-2(n) --> F-2(n), and (c) a permutation pi is an element of S-n. The function F-i,F-Y update the state of vertex i as a function of the states of vertex i and its Y-neighbors and leaves all other states invariant. By composing these functions in the order given by pi, we obtain the SDS [F-Y, pi] = (n)Pi (i=1) F-pi (i),F-Y : F-2(n) --> F-2(n). In this paper, we give a combinatorial upper bound for the number of non-equivalent SDS for a given graph, and we compute this bound explicitly for certain classes of graphs. We give a full characterization of invertible SDS; and analyze the set of fixed points of sequential and parallel cellular automata. Further, we introduce the concept of Maj-type SDS and show that systems of this class only have fixed points as attractors. Finally, we analyze SDS that are fixed point free for arbitrary base graphs. Published by Elsevier Science Inc.