Representing Reversible Cellular Automata with Reversible Block Cellular Automata

Abstract : 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).
Type de document :
Communication dans un congrès
Cori, Robert and Mazoyer, Jacques and Morvan, Michel and Mosseri, Rémy. Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, 2001, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001), pp.145-154, 2001, DMTCS Proceedings
Liste complète des métadonnées


https://hal.inria.fr/hal-01182977
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 6 août 2015 - 14:40:34
Dernière modification le : mardi 7 mars 2017 - 15:00:28
Document(s) archivé(s) le : mercredi 26 avril 2017 - 09:45:44

Fichier

dmAA0110.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01182977, version 1

Collections

Citation

Jérôme Durand-Lose. Representing Reversible Cellular Automata with Reversible Block Cellular Automata. Cori, Robert and Mazoyer, Jacques and Morvan, Michel and Mosseri, Rémy. Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, 2001, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001), pp.145-154, 2001, DMTCS Proceedings. <hal-01182977>

Partager

Métriques

Consultations de
la notice

269

Téléchargements du document

47