Discrete dynamical systems on graphs and Boolean functions

Chris L Barrett, William Y.C Chen and Michelle J Zheng

Mathematics and Computers in Simulation (MATCOM), 2004, vol. 66, issue 6, 487-497

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 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.

Keywords: Parallel dynamical system (PDS); Sequential dynamical system (SDS); Garden-of-Eden (GOE); State space; Fixed point; Periodic point (search for similar items in EconPapers)
Date: 2004
References: View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378475404000825
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matcom:v:66:y:2004:i:6:p:487-497

DOI: 10.1016/j.matcom.2004.03.003

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().