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.
Type de document :
Communication dans un congrès
20th International Symposium on Fundamentals of Computation Theory, Aug 2015, Gdańsk, Poland. 9210, pp.14, 2015, Fundamentals of Computation Theory. <10.1007/978-3-319-22177-9_27>
Liste complète des métadonnées

https://hal.inria.fr/hal-01249272
Contributeur : Simon Perdrix <>
Soumis le : jeudi 31 décembre 2015 - 10:28:37
Dernière modification le : mardi 21 février 2017 - 01:09:27

Identifiants

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. 9210, pp.14, 2015, Fundamentals of Computation Theory. <10.1007/978-3-319-22177-9_27>. <hal-01249272>

Partager

Métriques

Consultations de la notice

155