Outer-totalistic cellular automata on graphs

DOI10.1016/J.PHYSLETA.2008.12.013MaRDI QIDQ649684zbMATHOpenAlexFDO

Authors Carsten Marr, Marc-Thorsten Hütt

Publication date 5 December 2011

Published in Physics Letters. A (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Association schemes, strongly regular graphs (05E30) Dynamical aspects of cellular automata (37B15) Dynamical systems over complex numbers (37F99) Cellular automata (computational aspects) (68Q80)

Abstract: We present an intuitive formalism for implementing cellular automata on arbitrary topologies. By that means, we identify a symmetry operation in the class of elementary cellular automata. Moreover, we determine the subset of topologically sensitive elementary cellular automata and find that the overall number of complex patterns decreases under increasing neighborhood size in regular graphs. As exemplary applications, we apply the formalism to complex networks and compare the potential of scale-free graphs and metabolic networks to generate complex dynamics.

Recommendations

• Outer median and probabilistic cellular automata on network topologies
• Topology-induced phase transitions in totalistic cellular automata
• Cellular automata on graphs: topological properties of ER graphs evolved towards low-entropy dynamics
• scientific article; zbMATH DE number 4180823
• On the topological sensitivity of cellular automata

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• Cellular automaton modeling of biological pattern formation. Characterization, applications, and analysis. With a foreword by Philip K. Maini
• Efficient system-wide coordination in noisy environments
• Emergence of Scaling in Random Networks
• Emergence of complex dynamics in a simple model of signaling networks
• PERFORMANCE AND ROBUSTNESS OF CELLULAR AUTOMATA COMPUTATION ON IRREGULAR NETWORKS
• Statistical mechanics of cellular automata
• Statistical mechanics of complex networks
• The Structure and Function of Complex Networks
• The evolution of emergent computation.

Cited in

(12)

• Life-like network automata descriptor based on binary patterns for network classification
• Invertible behavior in elementary cellular automata with memory
• Cellular automata on graphs: topological properties of ER graphs evolved towards low-entropy dynamics
• A comprehensive taxonomy of cellular automata
• scientific article; zbMATH DE number 7180024 (Why is no real title available?)
• Outer median and probabilistic cellular automata on network topologies
• Topology-induced phase transitions in totalistic cellular automata
• A survey of cellular automata: types, dynamics, non-uniformity and applications
• Counting and hardness-of-finding fixed points in cellular automata on random graphs
• On arbitrarily long periodic orbits of evolutionary games on graphs
• Complexity index of outer-totalistic binary cellular automata with arbitrary dimension and neighborhood
• Cellular automata on irregular tessellations

This page was built for publication: Outer-totalistic cellular automata on graphs

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