Cycle Equivalence of Graph Dynamical Systems

Details Cycle Equivalence of Graph Dynamical Systems Cycle Equivalence of Graph Dynamical Systems

2008-02-29

arxiv.org/abs/0802.4412v1

Nonlinearity 22 (2009) 421-436.

Mathematics

Dynamical Systems

Scientific paper

10.1088/0951-7715/22/2/010

Graph dynamical systems (GDSs) can be used to describe a wide range of distributed, nonlinear phenomena. In this paper we characterize cycle equivalence of a class of finite GDSs called sequential dynamical systems SDSs. In general, two finite GDSs are cycle equivalent if their periodic orbits are isomorphic as directed graphs. Sequential dynamical systems may be thought of as generalized cellular automata, and use an update order to construct the dynamical system map. The main result of this paper is a characterization of cycle equivalence in terms of shifts and reflections of the SDS update order. We construct two graphs C(Y) and D(Y) whose components describe update orders that give rise to cycle equivalent SDSs. The number of components in C(Y) and D(Y) is an upper bound for the number of cycle equivalence classes one can obtain, and we enumerate these quantities through a recursion relation for several graph classes. The components of these graphs encode dynamical neutrality, the component sizes represent periodic orbit structural stability, and the number of components can be viewed as a system complexity measure.

Affiliated with

Also associated with

No associations

Rating

Cycle Equivalence of Graph Dynamical Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cycle Equivalence of Graph Dynamical Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cycle Equivalence of Graph Dynamical Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-353151