Skip to Main content Skip to Navigation
New interface
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 metadata
Contributor : Simon Perdrix Connect in order to contact the contributor
Submitted on : Thursday, December 31, 2015 - 10:28:37 AM
Last modification on : Thursday, August 4, 2022 - 4:53:43 PM



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