Outer-totalistic cellular automata on graphs

DOI10.1016/J.PHYSLETA.2008.12.013zbMATH Open1227.37006arXiv0812.2408OpenAlexW2034286445MaRDI QIDQ649684FDOQ649684

Authors: Carsten Marr, Marc-Thorsten Hütt 

Publication date: 5 December 2011

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

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.

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

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
• On the topological sensitivity of cellular automata

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)

Cites Work

• Statistical mechanics of complex networks
• Emergence of Scaling in Random Networks
• Title not available (Why is that?)
• The Structure and Function of Complex Networks
• Statistical mechanics of cellular automata
• Title not available (Why is that?)
• The evolution of emergent computation.
• 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 complex dynamics in a simple model of signaling networks
• PERFORMANCE AND ROBUSTNESS OF CELLULAR AUTOMATA COMPUTATION ON IRREGULAR NETWORKS

Cited In (13)

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

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)