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

https://hal.inria.fr/hal-01249272
Contributor : Simon Perdrix <>
Submitted on : Thursday, December 31, 2015 - 10:28:37 AM
Last modification on : Wednesday, April 3, 2019 - 1:23:13 AM

Identifiers

Citation

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⟩

Share

Metrics

Record views

303