Paper Info
Title
Representing Reversible Cellular Automata with Reversible Block Cellular Automata
Abstract
Cellular automata are mappings over infinite lattices such t hat 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 blo cks. We prove that any d-dimensional reversible cellular automaton can be expressed 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 infi nite configurations. This proves a 1990 conjecture by Toffoli and Margolus (Physica D 45) improved by Kari in 1996 (Mathematical System Theory29).
Year
Venue
Keywords
2001
DM-CCG
reversibility,partitioning cellular automata.,block cellular automata,cellular automata,linear time,cellular automaton
Field
DocType
Citations 
Quantum finite automata,Discrete mathematics,Cellular automaton,Combinatorics,Permutation,Reversible cellular automaton,Block cellular automaton,Partition (number theory),Time complexity,Mathematics,Toffoli gate
Conference
6
PageRank 
References 
Authors
0.97
8
1
Name
Order
Citations
PageRank
Jérôme Durand-Lose112714.93