Jérôme Durand-Lose - Representing Reversible Cellular Automata with Reversible Block Cellular Automata

dmtcs:2297 - Discrete Mathematics & Theoretical Computer Science, January 1, 2001, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001) - https://doi.org/10.46298/dmtcs.2297
Representing Reversible Cellular Automata with Reversible Block Cellular Automata

Authors: Jérôme Durand-Lose ORCID-iD1

  • 1 Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis

Cellular automata are mappings over infinite lattices such that each cell is updated according tothe states around it and a unique local function.Block permutations are mappings that generalize a given permutation of blocks (finite arrays of fixed size) to a given partition of the lattice in blocks.We prove that any d-dimensional reversible cellular automaton can be exp ressed as thecomposition of d+1 block permutations.We built a simulation in linear time of reversible cellular automata by reversible block cellular automata (also known as partitioning CA and CA with the Margolus neighborhood) which is valid for both finite and infinite configurations. This proves a 1990 conjecture by Toffoli and Margolus <i>(Physica D 45)</i> improved by Kari in 1996 <i>(Mathematical System Theory 29)</i>.


Volume: DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001)
Section: Proceedings
Published on: January 1, 2001
Imported on: November 21, 2016
Keywords: Cellular automata,reversibility,block cellular automata,partitioning cellular automata,[INFO] Computer Science [cs],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.tcs.2004.11.021
  • 10.1016/j.tcs.2004.11.021
Theory of cellular automata: a survey

11 Documents citing this article

Consultation statistics

This page has been seen 286 times.
This article's PDF has been downloaded 195 times.