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 Fi,Y:F2n→F2n, and (c) a permutation π∈Sn. The function Fi,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 π, we obtain the SDS[FY,π]=∏i=1nFπ(i),Y:F2n→F2n.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.