Friday 20 November 2015, 10:30, LSV: Reversible Causal Graph Dynamics, Simon Martiel.

Causal Graph Dynamics (CGD) extend Cellular Automata (CA) 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. First, we will generalize a classical result of reversible CA theory, stating that the inverse of any bijective CA is a CA. We will show a non trivial collateral result in the form of a Lavoisier-like preservation law of the number of vertices under the action of a reversible CGD. Finally, using these two results, we will provide a way of decomposing any reversible CGD as a bounded depth circuit of local, reversible operations. This is a joint work with Pablo Arrighi and Simon Perdrix.