Laboratoire Bordelais de Recherche en Informatique

Niveau: Supérieur
Laboratoire Bordelais de Recherche en Informatique, ura cnrs 1 304, Université Bordeaux I, 351, cours de la Libération, 33 405 Talence Cedex, France. Rapport de Recherche Numéro 1135-96 Any Reversible Cellular Automaton Can be Represented with Block Permutations Jérôme Olivier Durand-Lose labri, ura cnrs 1 304, Université Bordeaux I, 351, cours de la Libération, F-33 405 Talence Cedex, France. Abstract Cellular Automata are mappings such that each cell is updated according to the states around it and a unique local function. Block Permutations are mappings that divide partitions regularly in rectangular blocks of states and make the same permutations on each block. We prove that any d-dimensional Reversible Cellular Automata (d-r-ca) can be expressed as the restriction of a composition of 2 d Block Permutations (bp). We exhibit such representation for any d-r-ca with 2 d bp of width 6r. We also give a construction with d+ 1 bp, but with width 3(d + 1)r. 1 Introduction Cellular Automata (ca) provide the most famous model for parallel phenomena, computations and architec- tures. They operate as iterative systems on d-dimensional innite arrays, the underlying space is Z d .

• block permutation


• old states


• cellular automaton


• all natural


• over


• unique local function


• inverse block


• any reversible