On Theoretical Issues of Computer Simulations Sequential Dynamical Systems

摘要

This paper is a short version of [3]. We study a class of discrete dynamical systems that is motivated by the generic structure of simulations. The systems consists of the following data: (a) a finite graph Y with vertex set {1,...,n} where each vertex has a binary state, (b) functions F_i : F~n_2 and (c) an update ordering #pi#. The functions F_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. By composign the functiosn F_i in the order given by #pi# one obtains the dynamical system (Y, #pi#) = #PI#_(i=1)~nF_#pi#(i) : F_2~n -> F_2~n, i.e., a representative for the equivalence class of sequential dynamical systems [Y,#pi#] = {(Y,#pi#') = (Y,#pi#)} which we refer to as Sds. We derive a decomposition result, characterize invertibel Sds and study fixed points. In particular we analyse how many different Sds that can be obtained by reordering a given multiset of update functiosn and give a criterion for when one can derive concentration results on this number. Finally, some specific Sds are investigated.