Elements of a theory of simulation II: sequential dynamical systems

摘要

We study a class of discrete dynamical systems that is motivated by the generic structure of simulations. The systems consist of the following data: (a) a finite graph Y with vertex set {1,…,n} where each vertex has a binary state, (b) functions Fi:F2n→F2n and (c) an update ordering π. The functions Fi update the binary state of vertex i as a function of the state of vertex i and its Y-neighbors and leave the states of all other vertices fixed. The update ordering is a permutation of the Y-vertices. By composing the functions Fi in the order given by π one obtains the sequential dynamical system (SDS):[FY,π]=∏i=1nFπ(i):F2n→F2n.We derive a decomposition result, characterize invertible SDS and study fixed points. In particular we analyse how many different SDS that can be obtained by reordering a given multiset of update functions and give a criterion for when one can derive concentration results on this number. Finally, some specific SDS are investigated.