Cycle equivalence of graph dynamical systems

DOI10.1088/0951-7715/22/2/010MaRDI QIDQ3605110zbMATH OpenOpenAlexWikidataFDO

Authors M. Macauley, Henning S. Mortveit

Publication date 20 February 2009

Published in Nonlinearity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0802.4412

zbMATH Keywords

cellular automatoncycle equivalencegraph dynamical systemsequential dynamical system

Mathematics Subject Classification ID

Reflection and Coxeter groups (group-theoretic aspects) (20F55) Dynamical aspects of cellular automata (37B15) Combinatorial dynamics (types of periodic orbits) (37E15) Dynamical systems involving maps of trees and graphs (37E25)

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

Recommendations

• Cycle equivalence of finite dynamical systems containing symmetries
• Elements of a theory of simulation. III: Equivalence of SDS.
• Combinatorics of sequential dynamical systems
• Discrete, sequential dynamical systems
• ETS IV: Sequential dynamical systems: fixed points, invertibility and equivalence

Cited in

(16)

• Existence and non existence of limit cycles in Boolean networks
• Solutions to all-colors problem on graph cellular automata
• Attractor stability in finite asynchronous biological system models
• On enumeration of conjugacy classes of Coxeter elements
• An atlas of limit set dynamics for asynchronous elementary cellular automata
• Attractor stability in nonuniform Boolean networks
• Coxeter groups and asynchronous cellular automata
• Cyclic automata networks on finite graphs
• Update sequence stability in graph dynamical systems
• Effect of graph structure on the limit sets of threshold dynamical systems
• Cycle equivalence of finite dynamical systems containing symmetries
• Asynchronous, finite dynamical systems
• Complexity of limit cycles with block-sequential update schedules in conjunctive networks
• Lipschitz continuity under toric equivalence for asynchronous Boolean networks
• Period-3 orbits of sequential dynamical systems and their relationship to error-correcting codes over finite fields
• Flexible toggles and symmetric invertible asynchronous elementary cellular automata

This page was built for publication: Cycle equivalence of graph dynamical systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3605110)