Theoretical issues of computer simulations sequential dynamical systems

摘要

The authors study a class of discrete dynamical systems that is motivated by the generic structure of simulations. The systems consist of (a) a finite graph Y with vertex set (1,...,n) where each vertex has a binary state, (b) functions F(sub i):F(sub 2)(sup n) -> F(sub 2)(sup n) and (c) an update ordering (pi). The functions F(sub i) 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. They derive a decomposition result, characterize invertible SDS and study fixed points. In particular, they analyze 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.