Geodesic
Representing Reversible Cellular Automata with Reversible Block Cellular Automata
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001), DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001) (2001).

Voir la notice de l'article provenant de la source Episciences

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 <i>(Physica D 45)</i> improved by Kari in 1996 <i>(Mathematical System Theory 29)</i>. 
@article{DMTCS_2001_special_246_a20,
     author = {Durand-Lose, J\'er\^ome},
     title = {Representing {Reversible} {Cellular} {Automata} with {Reversible} {Block} {Cellular} {Automata}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001)},
     year = {2001},
     doi = {10.46298/dmtcs.2297},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2297/}
}
TY  - JOUR
AU  - Durand-Lose, Jérôme
TI  - Representing Reversible Cellular Automata with Reversible Block Cellular Automata
JO  - Discrete mathematics & theoretical computer science
PY  - 2001
VL  - DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2297/
DO  - 10.46298/dmtcs.2297
LA  - en
ID  - DMTCS_2001_special_246_a20
ER  - 
%0 Journal Article
%A Durand-Lose, Jérôme
%T Representing Reversible Cellular Automata with Reversible Block Cellular Automata
%J Discrete mathematics & theoretical computer science
%D 2001
%V DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2297/
%R 10.46298/dmtcs.2297
%G en
%F DMTCS_2001_special_246_a20
Durand-Lose, Jérôme. Representing Reversible Cellular Automata with Reversible Block Cellular Automata. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001), DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001) (2001). doi : 10.46298/dmtcs.2297. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2297/

Cité par Sources :