REDUCTION OF DISCRETE DYNAMICAL SYSTEMS OVER GRAPHS

H. S. Mortveit and C. M. Reidys
Additional contact information
H. S. Mortveit: Los Alamos National Laboratory, CCS-5, MS M997, Los Alamos, NM 87545, USA
C. M. Reidys: Los Alamos National Laboratory, CCS-5, MS M997, Los Alamos, NM 87545, USA

Advances in Complex Systems (ACS), 2004, vol. 07, issue 01, 1-20

Abstract: In this paper we study phase space relations in a certain class of discrete dynamical systems over graphs. The systems we investigate are called Sequential Dynamical Systems (SDSs), which are a class of dynamical systems that provide a framework for analyzing computer simulations. Specifically, an SDS consists of (i) a finite undirected graphYwith vertex set{1,2,…,n}where each vertex has associated a binary state, (ii) a collection ofY-local functions(Fi,Y)i∈v[Y]with$F_{i,Y}: \mathbb{F}_2^n\to \mathbb{F}_2^n$and (iii) a permutation π of the vertices ofY. The SDS induced by (i)–(iii) is the map\[ [F_Y,\pi] = F_{\pi(n),Y} \circ \cdots \circ F_{\pi(1),Y}\,. \]The paper is motivated by a general reduction theorem for SDSs which guarantees the existence of a phase space embedding induced by a covering map between the base graphs of two SDSs. We use this theorem to obtain information about phase spaces of certain SDSs over binary hypercubes from the dynamics of SDSs over complete graphs. We also investigate covering maps over binary hypercubes,$Q_2^n$, and circular graphs,Circn. In particular we show that there exists a covering map$\phi: Q_2^n\to K_{n+1}$if and only if2n≡0modn+1. Furthermore, we provide an interpretation of a class of invertible SDSs over circle graphs as right-shifts of lengthn-2over{0,1}2n-2. The paper concludes with a brief discussion of how we can extend a given covering map to a covering map over certain extended graphs.

Keywords: Sequential dynamical systems; graph morphisms; covering maps; phase space embeddings; reduction (search for similar items in EconPapers)
Date: 2004
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219525904000032
Access to full text is restricted to subscribers

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:wsi:acsxxx:v:07:y:2004:i:01:n:s0219525904000032

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219525904000032

Access Statistics for this article

Advances in Complex Systems (ACS) is currently edited by Frank Schweitzer

More articles in Advances in Complex Systems (ACS) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().