Geodesic
On the structure of the set of reversible cellular automata
Diskretnaya Matematika, Tome 19 (2007) no. 3, pp. 102-121

Voir la notice de l'article provenant de la source Math-Net.Ru

We investigate the structure of the set of reversible cellular automata. In the class of two-dimensional binary linear cellular automata with variable structure, the classes with decidable and undecidable reversibility property are separated, which contain almost all such cellular automata. With the use of this result, we prove undecidability of reversibility in the class of cellular automata with $\Gamma$-pattern and sixteen states of a cell and in the class of two-dimensional binary cellular automata with self-dual local transition functions. The complete description is given for the structure of the set of reversible cellular automata of the class of binary cellular automata with local transition functions from the Post classes. 
@article{DM_2007_19_3_a8,
     author = {I. V. Kucherenko},
     title = {On the structure of the set of reversible cellular automata},
     journal = {Diskretnaya Matematika},
     pages = {102--121},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_3_a8/}
}
TY  - JOUR
AU  - I. V. Kucherenko
TI  - On the structure of the set of reversible cellular automata
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 102
EP  - 121
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_3_a8/
LA  - ru
ID  - DM_2007_19_3_a8
ER  - 
%0 Journal Article
%A I. V. Kucherenko
%T On the structure of the set of reversible cellular automata
%J Diskretnaya Matematika
%D 2007
%P 102-121
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2007_19_3_a8/
%G ru
%F DM_2007_19_3_a8
I. V. Kucherenko. On the structure of the set of reversible cellular automata. Diskretnaya Matematika, Tome 19 (2007) no. 3, pp. 102-121. http://geodesic.mathdoc.fr/item/DM_2007_19_3_a8/