Representing Reversible Cellular Automata with Reversible Block Cellular Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2001

Representing Reversible Cellular Automata with Reversible Block Cellular Automata

Résumé

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 (Physica D 45) improved by Kari in 1996 (Mathematical System Theory 29).
Fichier principal
Vignette du fichier
dmAA0110.pdf (143.27 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01182977 , version 1 (06-08-2015)

Identifiants

Citer

Jérôme Durand-Lose. Representing Reversible Cellular Automata with Reversible Block Cellular Automata. Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, 2001, Paris, France. pp.145-154, ⟨10.46298/dmtcs.2297⟩. ⟨hal-01182977⟩
377 Consultations
830 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More