## 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