We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Reversible causal graph dynamics: invertibility, block representation, vertex-preservation.
- Authors
Arrighi, P.; Martiel, S.; Perdrix, S.
- Abstract
Causal Graph Dynamics extend Cellular Automata to arbitrary time-varying graphs of bounded degree. The whole graph evolves in discrete time steps, and this global evolution is required to have a number of 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. In particular, we extend two fundamental results on reversible cellular automata, by proving that the inverse of a causal graph dynamics is a causal graph dynamics, and that these reversible causal graph dynamics can be represented as finite-depth circuits of local reversible gates. We also show that reversible causal graph dynamics preserve the size of all but a finite number of graphs.
- Subjects
REPRESENTATIONS of graphs; CELLULAR automata; CAYLEY graphs; HAMILTONIAN graph theory
- Publication
Natural Computing, 2020, Vol 19, Issue 1, p157
- ISSN
1567-7818
- Publication type
Article
- DOI
10.1007/s11047-019-09768-0