Document Type

Article

Publication Date

1-2009

Publication Title

Nonlinearity

Volume

22

Issue

2

Publisher

IOP Publishing

Abstract

Graph dynamical systems (GDSs) generalize concepts such as cellular automata and Boolean networks and can describe a wide range of distributed, nonlinear phenomena. Two GDSs are cycle equivalent if their periodic orbits are isomorphic as directed graphs, which captures the notion of having comparable long-term dynamics. In this paper, we study cycle equivalence of GDSs in which the vertex functions are applied sequentially through an update sequence. The main result is a general characterization of cycle equivalence based on the underlying graph Y and the update sequences. We construct and analyse two graphs C(Y) and D(Y) whose connected components contain update sequences that induce cycle equivalent dynamical system maps. The number of components in these graphs, denoted κ(Y) and δ(Y), bound the number of possible long-term behaviour that can be generated by varying the update sequence. We give a recursion relation for κ(Y) which in turn allows us to enumerate δ(Y). The components of C(Y) and D(Y) characterize dynamical neutrality, their sizes represent structural stability of periodic orbits and the number of components can be viewed as a system complexity measure. We conclude with a computational result demonstrating the impact on complexity that results when passing from radius-1 to radius-2 rules in asynchronous cellular automata.

Comments

This manuscript has been published in the journal Nonlinearity. Please find the published version here (note that a subscription is necessary to access this version):

http://iopscience.iop.org/article/10.1088/0951-7715/22/2/010/meta

Download

Included in

Mathematics Commons

Share

COinS