Cycle equivalence of graph dynamical systems
Matthew Macauley, Henning Mortveit · Nonlinearity · 2009
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.