Discrete Dynamical Systems and Combinatorial Structures

 

Chris L. Barrett ^[1]

Los Alamos National Laboratory CCS-5, MS M997, Los Alamos, NM 87545, U.S.A.  

barrett@lanl.gov

 

Abstract.      Full Text PDF

 

Discrete dynamical systems based on dependency graphs have played an important role in the mathematical theory of computer simulations. We are concerned with parallel dynamical systems (PDS) and sequential dynamical systems (SDS) with all kinds of local functions, including arbitrary functions and symmetric Boolean functions. It has been recognized by Barrett, Mortveit and Reidys that PDS and SDS are closely related to combinatorial properties of the dependency graphs. Some properties of PDS and SDS over special dependency graphs are obtained. The number of distinct SDS on a dependency graph  is bounded by the number of acyclic orientations of . We present an evaluation scheme for PDS and SDS with the OR and NOR functions as local functions which can be used to clarify some basic properties of the dynamical systems. Furthermore, equivalent SDS, invertible SDS and probabilistic SDS are also studied.