Skip to Main content Skip to Navigation
Conference papers

Block Representation of Reversible Causal Graph Dynamics

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 study a further physics-like symmetry, namely reversibility. More precisely, we show that Reversible Causal Graph Dynamics can be represented as finite-depth circuits of local reversible gates.
Document type :
Conference papers
Complete list of metadatas
Contributor : Simon Perdrix <>
Submitted on : Thursday, December 31, 2015 - 10:28:37 AM
Last modification on : Tuesday, October 13, 2020 - 3:10:36 AM



Pablo Arrighi, Simon Martiel, Simon Perdrix. Block Representation of Reversible Causal Graph Dynamics. 20th International Symposium on Fundamentals of Computation Theory, Aug 2015, Gdańsk, Poland. pp.14, ⟨10.1007/978-3-319-22177-9_27⟩. ⟨hal-01249272⟩



Record views