Evaluation of the NOR Sequential Dynamical Systems

Thursday, November 6, 2003 - 9:20am - 9:55am
Keller 3-180
Henning Mortveit (Los Alamos National Laboratory)
William Y.C. Chen, Nankai University presented by Henning S. Mortveit, Los Alamos National Laboratory

Joint work with C.L. Barrett (Los Alamos National Laboratory, CCS-5, MS M997, Los Alamos, NM 87548, USA, and Michelle J. Zheng (Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, P.R. China)

We obtain an evaluation theorem for the sequential dynamical systems (SDS) based on the dependency graph G and the NOR update function. The importance of the NOR-SDS lies in both practical and theoretical considerations. From the graph theoretical point of view, the fixed points and Gardens-of-Eden of NOR-SDS are closely related to the independent sets of the underlying graph, as discovered by C. Reidys. Our evaluation theorem serves as a simplified algorithm of the update scheme given by the original definition.