Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001
Robert Cori and Jacques Mazoyer and Michel Morvan and Rémy Mosseri (eds.)
DMTCS Conference Volume AA (2001), pp. 145-154
| author: | Jérôme Durand-Lose |
|---|---|
| title: | Representing Reversible Cellular Automata with Reversible Block Cellular Automata |
| keywords: | Cellular automata, reversibility, block cellular automata, partitioning cellular automata |
| abstract: | Cellular automata are mappings over infinite lattices such that each cell is updated according to the 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 the composition 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). |
| If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. | |
| reference: | Jérôme Durand-Lose (2001), Representing Reversible Cellular Automata with Reversible Block Cellular Automata, in Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, Robert Cori and Jacques Mazoyer and Michel Morvan and Rémy Mosseri (eds.), Discrete Mathematics and Theoretical Computer Science Proceedings AA, pp. 145-154 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dmAA0110.ps.gz (44 K) |
| ps-source: | dmAA0110.ps (152 K) |
| pdf-source: | dmAA0110.pdf (107 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.
Automatically produced on Di Sep 27 10:09:03 CEST 2005 by gustedt
