Reversible causal graph dynamics

DOI10.1007/978-3-319-40578-0_5MaRDI QIDQ3186585zbMATH OpenOpenAlexFDO

Authors Pablo Arrighi, Simon Martiel, Simon Perdrix

Publication date 10 August 2016

Published in Reversible Computation (Search for Journal in Brave)

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

zbMATH Keywords

causal graph dynamicsCayley graphsinvertibilityreversible cellular automatashift invariance

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cellular automata (computational aspects) (68Q80)

Abstract: Causal Graph Dynamics extend Cellular Automata to arbitrary, bounded-degree, time-varying graphs. The whole graph evolves in discrete time steps, and this global evolution is required to have a number of physics-like symmetries: shift-invariance (it acts everywhere the same) and causality (information has a bounded speed of propagation). We add a further physics-like symmetry, namely reversibility. KEYWORDS: Bijective, invertible, injective, surjective, one-to-one, onto, Cayley graphs, Hedlund, Block representation, Lattice-gas automaton, Reversible Cellular Automata.

Recommendations

• Block representation of reversible causal graph dynamics
• Causal graph dynamics
• An intrinsically universal family of causal graph dynamics
• Intrinsic universality of causal graph dynamics
• Cellular automata reversible over limit set

Cites work

• Amalgamation of graph transformations: a synchronization mechanism
• Block representation of reversible causal graph dynamics
• Causal Graph Dynamics
• Endomorphisms and automorphisms of the shift dynamical system
• Endomorphisms of symbolic algebraic varieties
• Formal molecular biology
• Graph automata: Natural expression of self-reproduction
• scientific article; zbMATH DE number 1339963 (Why is no real title available?)
• scientific article; zbMATH DE number 1741020 (Why is no real title available?)
• Parallel and distributed derivations in the single-pushout approach
• Parallel high-level replacement systems
• Representation of reversible cellular automata with block permutations
• Reversibility of 2D cellular automata is undecidable
• Reversible simulation of one-dimensional irreversible cellular automata
• Synchronised Hyperedge Replacement as a Model for Service Oriented Computing
• Unitarity plus causality implies localizability

Cited in

(8)

• Causal graph dynamics
• An intrinsically universal family of causal graph dynamics
• Block representation of reversible causal graph dynamics
• Causal reversibility in Bayesian networks
• Intrinsic universality of causal graph dynamics
• Topological reversibility and causality in feed-forward networks
• Reversibility vs Local Creation/Destruction
• Reversible causal graph dynamics: invertibility, block representation, vertex-preservation

This page was built for publication: Reversible causal graph dynamics

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