Abstract:  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 dyn-amical 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.

  AMS Classification:  37B99, 68Q20.

  Keywords:   Parallel dynamical system (PDS), sequential dynamical system (SDS), Garden of Eden (GOE), state space,  fixed point, periodic  point.

  Download: pdf    ps    tex