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 F-i : F-2(n) --> F-2(n) 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 composing the functions F-i in the order given by pi one obtains the sequential dynamical system (SDs): [GRAPHICS] 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. (C) 2000 Elsevier Science Inc. All rights reserved.