Discrete dynamical systems on graphs and Boolean functions

Discrete dynamical systems based on dependency graphs have played an important role in the mathematical theory of computer simulations. In this paper, we are concerned with parallel dynamical systems (PDS) and sequential dynamical systems (SDS) with the OR and NOR functions as local functions. It has been recognized by Barrett, Mortveit and Reidys that SDS with the NOR function are closely related to combinatorial properties of the dependency graphs. We present an evaluation scheme for systems with the OR and NOR functions which can be used to clarify some basic properties of the dynamical systems. We show that for forests that does not contain a single edge the number of orientations equals the number of different OR-SDS. [Copyright &y& Elsevier]